algoadvance

You are given two strings s1 and s2, both of the same length. You can perform the following operation any number of times:

• Swap the characters at any two even indices.
• Swap the characters at any two odd indices.

Return true if you can make the strings s1 and s2 equal, and false otherwise.

Example:

• Input: s1 = "abcd", s2 = "cdab"
• Output: true
• Explanation:
  • Swap s1[1] with s1[3] results in "adcb"
  • Swap s1[0] with s1[2] results in "cdab"

Clarifying Questions

1. Are the given strings guaranteed to be of the same length, and what is the range of their length?
   • Yes, the problem states they are of the same length.
2. What characters do the strings contain?
   • The problem does not specify, so we should assume any characters allowed in standard strings.
3. Is case sensitivity considered in this problem?
   • Yes, case sensitivity should be considered as typical string comparison.

Strategy

To determine if we can make s1 equal to s2 using the allowed operations, let’s break it down:

1. Separate the characters at even indices and odd indices in both strings.
2. Sort the characters at even indices and the odd indices separately for both strings.
3. Compare the sorted characters of even indices and the sorted characters of odd indices for both strings.
4. If both comparisons match, then we can transform s1 to s2 using the allowed operations; otherwise, we cannot.

Code

Here’s the implementation of the described strategy:

def canBeMadeEqual(s1: str, s2: str) -> bool:
    if len(s1) != len(s2):
        return False

    even_indices_s1 = sorted(s1[i] for i in range(0, len(s1), 2))
    odd_indices_s1 = sorted(s1[i] for i in range(1, len(s1), 2))

    even_indices_s2 = sorted(s2[i] for i in range(0, len(s2), 2))
    odd_indices_s2 = sorted(s2[i] for i in range(1, len(s2), 2))

    return even_indices_s1 == even_indices_s2 and odd_indices_s1 == odd_indices_s2

# Example usage:
s1 = "abcd"
s2 = "cdab"
print(canBeMadeEqual(s1, s2))  # Output: True

Time Complexity

• Separation of characters: O(n) where n is the length of the strings.
• Sorting: O(n log n) for both even and odd indices.
• Comparison: O(n).

Overall, the time complexity is dominated by the sorting step, so it is O(n log n).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?