1540. Can Convert String in K Moves

Approach 1: Two Pass

• Time: $O(|\texttt{s}|)$
• Space: $O(26) = O(1)$

C++JavaPython

class Solution {
 public:
  bool canConvertString(string s, string t, int k) {
    if (s.length() != t.length())
      return false;

    // e.g. s = "aab", t = "bbc", so shiftCount[1] = 3
    // 1. a -> b, need 1 move.
    // 2. a -> b, need 1 + 26 moves.
    // 3. b -> c, need 1 + 26 * 2 moves.
    vector<int> shiftCount(26);

    for (int i = 0; i < s.length(); ++i)
      ++shiftCount[(t[i] - s[i] + 26) % 26];

    for (int shift = 1; shift < 26; ++shift)
      if (shift + 26 * (shiftCount[shift] - 1) > k)
        return false;

    return true;
  }
};

class Solution {
  public boolean canConvertString(String s, String t, int k) {
    if (s.length() != t.length())
      return false;

    // e.g. s = "aab", t = "bbc", so shiftCount[1] = 3
    // 1. a -> b, need 1 move.
    // 2. a -> b, need 1 + 26 moves.
    // 3. b -> c, need 1 + 26 * 2 moves.
    int[] shiftCount = new int[26];

    for (int i = 0; i < s.length(); ++i)
      ++shiftCount[(t.charAt(i) - s.charAt(i) + 26) % 26];

    for (int shift = 1; shift < 26; ++shift)
      if (shift + 26 * (shiftCount[shift] - 1) > k)
        return false;

    return true;
  }
}

class Solution:
  def canConvertString(self, s: str, t: str, k: int) -> bool:
    if len(s) != len(t):
      return False

    # e.g. s = "aab", t = "bbc", so shiftCount[1] = 3
    # 1. a -> b, need 1 move.
    # 2. a -> b, need 1 + 26 moves.
    # 3. b -> c, need 1 + 26 * 2 moves.
    shiftCount = [0] * 26

    for a, b in zip(s, t):
      shiftCount[(ord(b) - ord(a) + 26) % 26] += 1

    for shift in range(1, 26):
      if shift + 26 * (shiftCount[shift] - 1) > k:
        return False

    return True

Approach 2: One Pass

• Time: $O(|\texttt{s}|)$
• Space: $O(26) = O(1)$

C++JavaPython

class Solution {
 public:
  bool canConvertString(string s, string t, int k) {
    if (s.length() != t.length())
      return false;

    // e.g. s = "aab", t = "bbc", so shiftCount[1] = 3.
    // 1. a -> b, need 1 move.
    // 2. a -> b, need 1 + 26 moves.
    // 3. b -> c, need 1 + 26 * 2 moves.
    vector<int> shiftCount(26);

    for (int i = 0; i < s.length(); ++i) {
      const int shift = (t[i] - s[i] + 26) % 26;
      if (shift == 0)
        continue;
      if (shift + 26 * shiftCount[shift] > k)
        return false;
      ++shiftCount[shift];
    }

    return true;
  }
};

class Solution {
  public boolean canConvertString(String s, String t, int k) {
    if (s.length() != t.length())
      return false;

    // e.g. s = "aab", t = "bbc", so shiftCount[1] = 3
    // 1. a -> b, need 1 move.
    // 2. a -> b, need 1 + 26 moves.
    // 3. b -> c, need 1 + 26 * 2 moves.
    int[] shiftCount = new int[26];

    for (int i = 0; i < s.length(); ++i) {
      final int shift = (t.charAt(i) - s.charAt(i) + 26) % 26;
      if (shift == 0)
        continue;
      if (shift + 26 * shiftCount[shift] > k)
        return false;
      ++shiftCount[shift];
    }

    return true;
  }
}

class Solution:
  def canConvertString(self, s: str, t: str, k: int) -> bool:
    if len(s) != len(t):
      return False

    # e.g. s = "aab", t = "bbc", so shiftCount[1] = 3
    # 1. a -> b, need 1 move.
    # 2. a -> b, need 1 + 26 moves.
    # 3. b -> c, need 1 + 26 * 2 moves.
    shiftCount = [0] * 26

    for a, b in zip(s, t):
      shift = (ord(b) - ord(a) + 26) % 26
      if shift == 0:
        continue
      if shift + 26 * shiftCount[shift] > k:
        return False
      shiftCount[shift] += 1

    return True