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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Can Convert String in K Moves

Difficulty: Medium

Problem Description

Given two strings s and t, your goal is to convert s into t in k moves or less. During each move, you can choose an index from s and shift the character at that index a certain number of times in the alphabet. You must determine if it is possible to convert s to t within the given constraints.

Key Insights

  • Each character in s can be shifted to any character by wrapping around the alphabet.
  • The number of shifts needed to convert a character from s to t can be calculated using modular arithmetic.
  • The total number of moves cannot exceed k, and each index can only be chosen once.
  • If the total required shifts exceed k or if there are not enough distinct indices to perform the shifts, the conversion is not possible.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the strings, as we need to iterate through each character to compute the shifts. Space Complexity: O(1), as we are using a constant amount of space for counters and temporary variables.

Solution

To solve this problem, we will:

  1. Iterate through each character in both strings s and t.
  2. Calculate the required shifts for each character in s to match the corresponding character in t using modular arithmetic.
  3. Sum all the required shifts.
  4. Check if the total shifts can be completed within k moves, considering the number of distinct characters we need to shift.

We will use simple integer arithmetic and a loop to achieve this.

Code Solutions

def can_convert_string(s, t, k):
    if len(s) != len(t):
        return False
    
    shifts_needed = 0
    shifts_counts = [0] * 26  # For each letter a-z

    for cs, ct in zip(s, t):
        shift = (ord(ct) - ord(cs)) % 26
        shifts_counts[shift] += 1
        shifts_needed += shift

    # Check if we can convert within k moves
    for i in range(1, 26):
        if shifts_counts[i] > 0:
            max_shifts = i * shifts_counts[i]  # Maximum shifts needed for this character
            if max_shifts > k:  # If we exceed k, return false
                return False
            k -= max_shifts  # Reduce k by the number of shifts we can afford

    return shifts_needed <= k
← Back to All Questions