<p>Given two strings&nbsp;<code>s</code>&nbsp;and&nbsp;<code>t</code>, your goal is to convert&nbsp;<code>s</code>&nbsp;into&nbsp;<code>t</code>&nbsp;in&nbsp;<code>k</code><strong>&nbsp;</strong>moves or less.</p>

<p>During the&nbsp;<code>i<sup>th</sup></code>&nbsp;(<font face="monospace"><code>1 &lt;= i &lt;= k</code>)&nbsp;</font>move you can:</p>

<ul>
	<li>Choose any index&nbsp;<code>j</code>&nbsp;(1-indexed) from&nbsp;<code>s</code>, such that&nbsp;<code>1 &lt;= j &lt;= s.length</code>&nbsp;and <code>j</code>&nbsp;has not been chosen in any previous move,&nbsp;and shift the character at that index&nbsp;<code>i</code>&nbsp;times.</li>
	<li>Do nothing.</li>
</ul>

<p>Shifting a character means replacing it by the next letter in the alphabet&nbsp;(wrapping around so that&nbsp;<code>&#39;z&#39;</code>&nbsp;becomes&nbsp;<code>&#39;a&#39;</code>). Shifting a character by&nbsp;<code>i</code>&nbsp;means applying the shift operations&nbsp;<code>i</code>&nbsp;times.</p>

<p>Remember that any index&nbsp;<code>j</code>&nbsp;can be picked at most once.</p>

<p>Return&nbsp;<code>true</code>&nbsp;if it&#39;s possible to convert&nbsp;<code>s</code>&nbsp;into&nbsp;<code>t</code>&nbsp;in no more than&nbsp;<code>k</code>&nbsp;moves, otherwise return&nbsp;<code>false</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;input&quot;, t = &quot;ouput&quot;, k = 9
<strong>Output:</strong> true
<b>Explanation: </b>In the 6th move, we shift &#39;i&#39; 6 times to get &#39;o&#39;. And in the 7th move we shift &#39;n&#39; to get &#39;u&#39;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abc&quot;, t = &quot;bcd&quot;, k = 10
<strong>Output:</strong> false
<strong>Explanation: </strong>We need to shift each character in s one time to convert it into t. We can shift &#39;a&#39; to &#39;b&#39; during the 1st move. However, there is no way to shift the other characters in the remaining moves to obtain t from s.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aab&quot;, t = &quot;bbb&quot;, k = 27
<strong>Output:</strong> true
<b>Explanation: </b>In the 1st move, we shift the first &#39;a&#39; 1 time to get &#39;b&#39;. In the 27th move, we shift the second &#39;a&#39; 27 times to get &#39;b&#39;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length, t.length &lt;= 10^5</code></li>
	<li><code>0 &lt;= k &lt;= 10^9</code></li>
	<li><code>s</code>, <code>t</code> contain&nbsp;only lowercase English letters.</li>
</ul>

'''
\U0001f50e EXPLORE
What are some other insightful & revealing test cases?

k is the number of moves you have
- move means interation and shift

j is the index and can only be change one time


j had not been chosen in any previous move?



k = 9
i = 9
j = 1

        i
"b  b   c" 
"b  c   d"

                                   
abcdefgh i  j   k   l   m   n   o pkrstuvwxyz

\U0001f9e0 BRAINSTORM
What approaches could work?
Algorithm 1: interate while we have move lefts
Time: O(n) n -> number of moves
Space: O(m) m -> number of changed indexes
==================================================
example:
s = "input", t = "ouput"
k = 9

distance between the current character in s from t
    if it is equal to the move number, shift is done
    keep track of the index that was changed
    if move number is greater than 26 and distance == move number - 26:
            shift
    if i is grater than the distance move to next character
    update k by every move and shift 
    i = i%len(s)

i = 6
    i
1   2   3   4   5
i   n   p   u   t

\U0001f4c6 PLAN
Outline of algorithm 1: 






\U0001f6e0️ IMPLEMENT
Write your algorithm.
 

\U0001f9ea VERIFY
Run tests. Methodically debug & analyze issues.

s = "input", t = "ouput", k = 9

seenIndexes = ()
i = 5

length = len(s) # 5
while True:

index = 0
distance = 6

i
i   n   p   u   t

o   u   p   u   t
                                  
i j k l m n o p q r s u v w x y z 

we are allow at most k shifts
if at any point distance between characters is greater than k return false

every time i equals the distance we may apply the shift 

how do we know if there is going to be future i that will met the requriements?


'''
class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s)!=len(t):
            return False
        shifts = [0 for x in range(1, 27)]
        for i in range(len(s)):
            if s[i] == t[i]:
                continue
            diff = (ord(t[i]) - ord(s[i])) % 26
            if shifts[diff] * 26 + diff > k:
                return False
            shifts[diff]+=1
        return True

















17500