Skip to content

1540. Can Convert String in K Moves

Description

Given two stringsย sย andย t, your goal is to convertย sย intoย tย inย kย moves or less.

During theย ithย (1 <= i <= k)ย move you can:

  • Choose any indexย jย (1-indexed) fromย s, such thatย 1 <= j <= s.lengthย and jย has not been chosen in any previous move,ย and shift the character at that indexย iย times.
  • Do nothing.

Shifting a character means replacing it by the next letter in the alphabetย (wrapping around so thatย 'z'ย becomesย 'a'). Shifting a character byย iย means applying the shift operationsย iย times.

Remember that any indexย jย can be picked at most once.

Returnย trueย if it's possible to convertย sย intoย tย in no more thanย kย moves, otherwise returnย false.

ย 

Example 1:

Input: s = "input", t = "ouput", k = 9
Output: true
Explanation: In the 6th move, we shift 'i' 6 times to get 'o'. And in the 7th move we shift 'n' to get 'u'.

Example 2:

Input: s = "abc", t = "bcd", k = 10
Output: false
Explanation: We need to shift each character in s one time to convert it into t. We can shift 'a' to 'b' during the 1st move. However, there is no way to shift the other characters in the remaining moves to obtain t from s.

Example 3:

Input: s = "aab", t = "bbb", k = 27
Output: true
Explanation: In the 1st move, we shift the first 'a' 1 time to get 'b'. In the 27th move, we shift the second 'a' 27 times to get 'b'.

ย 

Constraints:

  • 1 <= s.length, t.length <= 10^5
  • 0 <= k <= 10^9
  • s, t containย only lowercase English letters.

Solutions

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        cnt = [0] * 26
        for a, b in zip(s, t):
            x = (ord(b) - ord(a) + 26) % 26
            cnt[x] += 1
        for i in range(1, 26):
            if i + 26 * (cnt[i] - 1) > k:
                return False
        return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean canConvertString(String s, String t, int k) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            int x = (t.charAt(i) - s.charAt(i) + 26) % 26;
            ++cnt[x];
        }
        for (int i = 1; i < 26; ++i) {
            if (i + 26 * (cnt[i] - 1) > k) {
                return false;
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool canConvertString(string s, string t, int k) {
        if (s.size() != t.size()) {
            return false;
        }
        int cnt[26]{};
        for (int i = 0; i < s.size(); ++i) {
            int x = (t[i] - s[i] + 26) % 26;
            ++cnt[x];
        }
        for (int i = 1; i < 26; ++i) {
            if (i + 26 * (cnt[i] - 1) > k) {
                return false;
            }
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func canConvertString(s string, t string, k int) bool {
    if len(s) != len(t) {
        return false
    }
    cnt := [26]int{}
    for i := range s {
        x := (t[i] - s[i] + 26) % 26
        cnt[x]++
    }
    for i := 1; i < 26; i++ {
        if i+26*(cnt[i]-1) > k {
            return false
        }
    }
    return true
}

Comments