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 II

Number: 2978

Difficulty: Medium

Paid? No

Companies: Citrix

Problem Description

Given two strings s1 and s2 of equal length composed of lowercase English letters, determine whether s1 can be transformed into s2 using the following operation any number of times on either string: choose any two indices i and j (with i < j) such that the difference (j - i) is even, then swap the characters at positions i and j. Since the swap operation only allows characters at indices of the same parity (even with even, odd with odd) to be swapped, decide whether the two strings can be made equal by reordering the characters in each parity group independently.

Key Insights

  • The swap operation only permits swaps between indices of the same parity, meaning even-indexed characters can only be swapped with even-indexed characters, and odd-indexed characters only with odd-indexed characters.
  • To transform s1 into s2, the collection (multiset) of even-indexed characters in s1 must match that in s2; the same must hold true for the odd-indexed characters.
  • Sorting or counting the frequency of characters in the even and odd positions separately for both strings can be used to verify if the transformation is possible.

Space and Time Complexity

Time Complexity: O(n log n) if sorting is used, where n is the length of the strings.
Space Complexity: O(n) to store the even and odd indexed characters for both strings.

Solution

We approach the problem by partitioning both s1 and s2 into two groups: one containing characters at even indices and the other containing characters at odd indices. Since swaps are only valid within each group, we can only rearrange the characters within even indices among themselves and similarly for odd indices. Therefore, to be able to transform s1 into s2, the sorted order or the multiset of even-indexed characters in s1 must exactly match that in s2, and the same condition must hold for odd-indexed characters.

We can achieve this by:

  1. Iterating over the indices of s1 and s2.
  2. Collecting the characters at even indices and odd indices separately for both strings.
  3. Sorting both even-index lists and comparing them, and doing the same for odd-index lists.
  4. If both comparisons are equal, return true; otherwise, false.

Data structures used include arrays (or lists) for collecting characters and built-in sorting algorithms for order comparison.

Code Solutions

# Python solution with comments

def canBeEqual(s1: str, s2: str) -> bool:
    # Separate characters by parity (even and odd indices)
    s1_even = [s1[i] for i in range(len(s1)) if i % 2 == 0]
    s1_odd = [s1[i] for i in range(len(s1)) if i % 2 != 0]
    s2_even = [s2[i] for i in range(len(s2)) if i % 2 == 0]
    s2_odd = [s2[i] for i in range(len(s2)) if i % 2 != 0]
    
    # Sort both lists to check for matching multisets
    return sorted(s1_even) == sorted(s2_even) and sorted(s1_odd) == sorted(s2_odd)

# Example usage:
print(canBeEqual("abcdba", "cabdab"))  # Expected output: True
print(canBeEqual("abe", "bea"))        # Expected output: False
← Back to All Questions