Check if Strings Can be Made Equal With Operations I

Difficulty: Easy | Acceptance: 61.90% | Paid: No Topics: String

You are given two strings s1 and s2 of equal length consisting of lowercase English letters.

In one operation, you can choose two indices i and j (0-indexed) such that i % 2 == j % 2 and swap s1[i] with s1[j].

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

• Examples
• Constraints
• Frequency Counting
• Sorting

Examples

Input: s1 = "abcd", s2 = "cdab"
Output: true
Explanation: One possible sequence of operations is:
- Swap indices 0 and 2, and indices 1 and 3. The string becomes "cdab".

Input: s1 = "abcd", s2 = "dacb"
Output: false
Explanation: It is impossible to make s1 equal to s2.

Constraints

1 <= s1.length == s2.length <= 100
s1 and s2 consist of lowercase English letters.

Frequency Counting

Intuition Since we can only swap characters at indices with the same parity (even with even, odd with odd), the multiset of characters at even indices in s1 must match the multiset of characters at even indices in s2. The same applies to odd indices.

Steps

• Initialize two frequency arrays (or hash maps) for even indices and two for odd indices.
• Iterate through the strings. For each index, increment the corresponding frequency counter based on whether the index is even or odd.
• Compare the frequency arrays for s1 and s2 for both even and odd indices.
• Return true if both comparisons match, otherwise false.

class Solution:
    def canBeEqual(self, s1: str, s2: str) -> bool:
        if len(s1) != len(s2):
            return False
        n = len(s1)
        # Even indices
        count_even_s1 = [0] * 26
        count_even_s2 = [0] * 26
        # Odd indices
        count_odd_s1 = [0] * 26
        count_odd_s2 = [0] * 26

        for i in range(n):
            char_code = ord(s1[i]) - ord('a')
            if i % 2 == 0:
                count_even_s1[char_code] += 1
            else:
                count_odd_s1[char_code] += 1

            char_code = ord(s2[i]) - ord('a')
            if i % 2 == 0:
                count_even_s2[char_code] += 1
            else:
                count_odd_s2[char_code] += 1

        return count_even_s1 == count_even_s2 and count_odd_s1 == count_odd_s2

Complexity

• Time: O(n)
• Space: O(1) (since the alphabet size is fixed at 26)
• Notes: This is the most optimal approach as it only requires a single pass through the strings.

Sorting

Intuition If we can rearrange characters at even indices freely, then sorting the characters at even indices of s1 should result in the same sequence as sorting the characters at even indices of s2. The same logic applies to odd indices.

Steps

• Extract characters at even indices from s1 and s2 into separate lists/arrays.
• Extract characters at odd indices from s1 and s2 into separate lists/arrays.
• Sort all four lists/arrays.
• Compare the sorted even lists and the sorted odd lists.
• Return true if both pairs are identical, otherwise false.

class Solution:
    def canBeEqual(self, s1: str, s2: str) -> bool:
        # Extract even and odd indices
        s1_even = sorted(s1[::2])
        s2_even = sorted(s2[::2])
        s1_odd = sorted(s1[1::2])
        s2_odd = sorted(s2[1::2])
        
        return s1_even == s2_even and s1_odd == s2_odd

Complexity

• Time: O(n log n) due to sorting.
• Space: O(n) to store the extracted characters.
• Notes: While intuitive, this is slightly less efficient than frequency counting due to the sorting step, but perfectly acceptable given the constraint n <= 100.