Can Convert String in K Moves

Can Convert String in K Moves

What is this problem about?

The Can Convert String in K Moves interview question asks if you can transform string s into string t using at most k moves. In the i-th move (where 1 <= i <= k), you can choose an index and shift the character there i times forward in the alphabet (with wrap-around from 'z' to 'a'). Each move i can be used exactly once. This Can Convert String in K Moves coding problem is about frequency tracking and mathematical cycle logic.

Why is this asked in interviews?

Infosys and other firms use this to test a candidate's ability to think about modular arithmetic and resource allocation. It’s not about string manipulation itself, but about whether the required "shift values" can all be provided within the k moves. It tests if you can identify that a shift of x is the same as x + 26, x + 52, etc.

Algorithmic pattern used

This follows the Hash Table, String interview pattern.

1. For each character pair (s[i], t[i]), calculate the required shift d.
2. If d = 0, ignore it.
3. If d > 0, you need a move of d, or d + 26, or d + 52...
4. Track the number of times each specific shift d (from 1 to 25) is needed. If you need a shift d for the m-th time, the required move number is d + (m-1) * 26.
5. If any required move number exceeds k, return false.

Example explanation

s = "abc", t = "bcd", k = 10

• index 0: 'a' to 'b' needs shift 1. Use move 1.
• index 1: 'b' to 'c' needs shift 1. We already used move 1. Use move 1 + 26 = 27.
• Wait, 27 > 10. So we cannot convert. Result: False. If k was 30, it would be possible.

Common mistakes candidates make

• Simulating shifts: Trying to actually change the characters in the string, which is unnecessary.
• Ignoring the cycle: Forgetting that after shift 26, you're back to where you started, so shift 27 is the same as shift 1 but requires a different move number.
• O(K) approach: Trying to iterate through moves 1 to k. Since k can be 10^9, you must use an O(N) approach where N is the string length.

Interview preparation tip

When a problem involves "moves" or "actions" numbered 1 to K and wrap-around logic, look for the relationship between the required change and the cycle length (like 26 for the alphabet). Modular arithmetic is your best friend here.