Skip to content

Latest commit

 

History

History
145 lines (100 loc) · 4.39 KB

README_EN.md

File metadata and controls

145 lines (100 loc) · 4.39 KB
Raw
comments difficulty edit_url rating source tags
true
Medium
1806
Weekly Contest 421 Q2
Hash Table
Math
String
Dynamic Programming
Counting

3335. Total Characters in String After Transformations I

中文文档

Description

You are given a string s and an integer t, representing the number of transformations to perform. In one transformation, every character in s is replaced according to the following rules:

  • If the character is 'z', replace it with the string "ab".
  • Otherwise, replace it with the next character in the alphabet. For example, 'a' is replaced with 'b', 'b' is replaced with 'c', and so on.

Return the length of the resulting string after exactly t transformations.

Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: s = "abcyy", t = 2

Output: 7

Explanation:

  • First Transformation (t = 1): 
    <ul>
	<li><code>&#39;a&#39;</code> becomes <code>&#39;b&#39;</code></li>
	<li><code>&#39;b&#39;</code> becomes <code>&#39;c&#39;</code></li>
	<li><code>&#39;c&#39;</code> becomes <code>&#39;d&#39;</code></li>
	<li><code>&#39;y&#39;</code> becomes <code>&#39;z&#39;</code></li>
	<li><code>&#39;y&#39;</code> becomes <code>&#39;z&#39;</code></li>
	<li>String after the first transformation: <code>&quot;bcdzz&quot;</code></li>
</ul>
</li>
<li><strong>Second Transformation (t = 2)</strong>:
<ul>
	<li><code>&#39;b&#39;</code> becomes <code>&#39;c&#39;</code></li>
	<li><code>&#39;c&#39;</code> becomes <code>&#39;d&#39;</code></li>
	<li><code>&#39;d&#39;</code> becomes <code>&#39;e&#39;</code></li>
	<li><code>&#39;z&#39;</code> becomes <code>&quot;ab&quot;</code></li>
	<li><code>&#39;z&#39;</code> becomes <code>&quot;ab&quot;</code></li>
	<li>String after the second transformation: <code>&quot;cdeabab&quot;</code></li>
</ul>
</li>
<li><strong>Final Length of the string</strong>: The string is <code>&quot;cdeabab&quot;</code>, which has 7 characters.</li>

Example 2:

Input: s = "azbk", t = 1

Output: 5

Explanation:

  • First Transformation (t = 1): 
    <ul>
	<li><code>&#39;a&#39;</code> becomes <code>&#39;b&#39;</code></li>
	<li><code>&#39;z&#39;</code> becomes <code>&quot;ab&quot;</code></li>
	<li><code>&#39;b&#39;</code> becomes <code>&#39;c&#39;</code></li>
	<li><code>&#39;k&#39;</code> becomes <code>&#39;l&#39;</code></li>
	<li>String after the first transformation: <code>&quot;babcl&quot;</code></li>
</ul>
</li>
<li><strong>Final Length of the string</strong>: The string is <code>&quot;babcl&quot;</code>, which has 5 characters.</li>

 

Constraints:

  • 1 <= s.length <= 105
  • s consists only of lowercase English letters.
  • 1 <= t <= 105

Solutions

Solution 1

Python3



Java




C++




Go