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

Check if Strings Can be Made Equal With Operations I

Number: 2999

Difficulty: Easy

Paid? No

Companies: Citrix

Problem Description

Given two strings s1 and s2 of length 4 each, determine if it is possible to make them equal by repeatedly swapping characters in either string at indices that are two apart (i.e. for any indices i and j such that j - i = 2). The operation allows swapping only between characters at positions with the same parity (even with even or odd with odd).

Key Insights

  • The swap operation only exchanges characters within the same parity positions.
  • To transform one string into another, characters at even indices of s1 must be rearrangeable to match those at even indices of s2, and similarly for odd indices.
  • Therefore, the necessary and sufficient condition is that the sorted/multiset of even-index characters in s1 equals that in s2, and the same for odd-index characters.

Space and Time Complexity

Time Complexity: O(n) where n = 4 (constant time in this problem, but conceptually O(n) for checking even and odd positions)
Space Complexity: O(n) for storing the characters from the even and odd positions

Solution

The solution is based on the observation that the allowed swap operation only permits exchanges between characters at indices of the same parity. This means we can independently rearrange the characters at the even indices and the characters at the odd indices. To determine if s1 can be transformed into s2, we compare the characters at even indices of both strings and the characters at odd indices of both strings. If both pairs of groups match (ignoring order), then the transformation is possible; otherwise, it is not.

Code Solutions

# Python solution with detailed comments
def canBeEqual(s1: str, s2: str) -> bool:
    # Extract even index characters for both s1 and s2
    s1_even = [s1[i] for i in range(0, len(s1), 2)]
    s2_even = [s2[i] for i in range(0, len(s2), 2)]
    # Extract odd index characters for both s1 and s2
    s1_odd = [s1[i] for i in range(1, len(s1), 2)]
    s2_odd = [s2[i] for i in range(1, len(s2), 2)]
    
    # Sort both even and odd character lists and compare
    return sorted(s1_even) == sorted(s2_even) and sorted(s1_odd) == sorted(s2_odd)

# Example usage
print(canBeEqual("abcd", "cdab"))  # Output: True
print(canBeEqual("abcd", "dacb"))  # Output: False
← Back to All Questions