We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Can Convert String in K Moves

Number: 1647

Difficulty: Medium

Paid? No

Companies: Infosys

Problem Description

Given two strings s and t, the goal is to convert s into t by performing at most k moves. In the i-th move (1 <= i <= k), you can select an index j (1-indexed and not chosen before) from s and shift the character at that index i times. Shifting a character means replacing it with its subsequent letter in the alphabet (with wrapping from 'z' to 'a'). Determine if it is possible to achieve the transformation in no more than k moves.

Key Insights

  • Compute the required shift for each character as (t[i] - s[i] + 26) % 26.
  • A shift of 0 indicates no change is needed.
  • For non-zero shifts, if the same shift is required multiple times, subsequent occurrences must be scheduled at least 26 moves apart.
  • Use a frequency count for each non-zero shift requirement to calculate the maximum move needed for that shift.
  • Ensure that the maximum move number required does not exceed k.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the strings. Space Complexity: O(1) since the frequency dictionary/array size is fixed (26 possible shifts).

Solution

The solution involves:

  1. Iterating through each character pair in s and t to calculate the required shift.
  2. Using a dictionary (or fixed array) to maintain the frequency of each shift (ignoring 0 shifts).
  3. For each shift value, calculating the maximum move number needed to schedule all its occurrences using the formula: move = shift + 26 * (count - 1).
  4. Comparing the maximum move required with k. If any exceed k, return false; otherwise, return true.

Code Solutions

# Python Solution
class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        # If the strings have different lengths, conversion is impossible.
        if len(s) != len(t):
            return False
        
        # Dictionary to count frequency for each shift value (1 to 25)
        shift_counts = {}
        
        # Compute required shift for each character
        for i in range(len(s)):
            diff = (ord(t[i]) - ord(s[i]) + 26) % 26
            if diff != 0:
                shift_counts[diff] = shift_counts.get(diff, 0) + 1
        
        # For each shift, compute the maximum move number needed
        for shift, count in shift_counts.items():
            max_move = shift + (count - 1) * 26
            if max_move > k:
                return False
        
        return True

# Example test
sol = Solution()
print(sol.canConvertString("input", "ouput", 9))  # Expected output: True
← Back to All Questions