Check if Strings Can be Made Equal With Operations II

Medium

Asked by:

7 views

Topics:

ArraysStrings

You are given two strings s1 and s2, both of length n, consisting of lowercase English letters.

You can apply the following operation on any of the two strings any number of times:

Choose any two indices i and j such that i < j and the difference j - i is even, then swap the two characters at those indices in the string.

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

Example 1:

Input: s1 = "abcdba", s2 = "cabdab"
Output: true
Explanation: We can apply the following operations on s1:
- Choose the indices i = 0, j = 2. The resulting string is s1 = "cbadba".
- Choose the indices i = 2, j = 4. The resulting string is s1 = "cbbdaa".
- Choose the indices i = 1, j = 5. The resulting string is s1 = "cabdab" = s2.

Example 2:

Input: s1 = "abe", s2 = "bea"
Output: false
Explanation: It is not possible to make the two strings equal.

Constraints:

n == s1.length == s2.length
1 <= n <= 10⁵
s1 and s2 consist only of lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Do allowed swaps only exchange positions whose distance is even, so even indexes never mix with odd indexes?
What should happen when the two strings have different lengths?
If the overall letters match but the even positions do not, is the answer no?
Should duplicate letters count as indistinguishable when arrangements are listed?
Is a yes or no enough, without returning the sequence of swaps?

Brute Force Solution

Approach

After rejecting different lengths or different overall letters, this search separates the first string into even-index characters and odd-index characters. It lists every distinct arrangement of each of those groups. It interleaves each pair of arrangements and returns true when any rebuilt string equals the target.

Here's how the algorithm would work step-by-step:

Return false when the lengths differ.
Return false when sorting the two strings does not produce the same sequence of characters.
Pull the even-index characters and the odd-index characters out of the first string.
Generate every distinct permutation of the even characters and of the odd characters.
For each pair of permutations, place the even characters back on even indexes and the odd characters on odd indexes.
Return true as soon as a rebuilt string equals the second string.
Return false when every pair has been tried without a match.

Code Implementation

from itertools import permutations

def can_be_made_equal_brute_force(first_string, second_string):
    if len(first_string) != len(second_string):
        return False

    # This initial check confirms if the strings have the same character multiset.
    # If they don't, no amount of swapping can make them equal.
    if sorted(first_string) != sorted(second_string):

        return False

    even_indexed_chars = [first_string[index] for index in range(0, len(first_string), 2)]
    odd_indexed_chars = [first_string[index] for index in range(1, len(first_string), 2)]

    even_permutations = set(permutations(even_indexed_chars))
    odd_permutations = set(permutations(odd_indexed_chars))

    # We must iterate through all possible arrangements of even and odd characters.
    # This represents every valid transformation of the first string.
    for even_perm in even_permutations:

        for odd_perm in odd_permutations:
            reconstructed_string_list = [''] * len(first_string)
            reconstructed_string_list[0::2] = even_perm
            reconstructed_string_list[1::2] = odd_perm

            # If any reconstructed string matches the target, it's a success.
            if "".join(reconstructed_string_list) == second_string:

                return True

    # After checking all valid permutations, if no match is found, it's impossible.
    return False

Big(O) Analysis

Time Complexity

O(n * ((n/2)!)^2) – About half of the n positions are even and about half are odd. Listing the distinct permutations of a half-length group is proportional to the factorial of n over two, times the half length, in the worst case where all characters differ. The search then pairs every even permutation with every odd permutation. Rebuilding one interleaving scans n positions. The nested pairing therefore costs O(n * ((n/2)!)^2).

Space Complexity

O(n * (n/2)!) – The even permutations and the odd permutations are stored before the nested loops begin. Each stored permutation holds about n over two characters, and there are up to the factorial of that many distinct ones. The string being rebuilt has length n and is reused. The recursion that builds a permutation is only as deep as the half length. The stored permutations dominate and use O(n * (n/2)!) space.

Optimal Solution

Approach

Swaps of even distance can reorder even positions freely and odd positions freely, but they cannot move a letter between those two groups. The strings match when their full letter counts match and, separately, when the even positions have the same counts and the odd positions have the same counts. Any mismatch in those counts is a no.

Here's how the algorithm would work step-by-step:

Compare the total letter counts of the two strings and return false if they differ.
Split the first string into the characters on even indexes and the characters on odd indexes.
Split the second string the same way.
Compare the even-position counts and return false on any difference.
Compare the odd-position counts and return false on any difference.
Return true when both position groups agree.

Code Implementation

from collections import Counter

def can_be_equal_with_ops_ii(string1, string2):
    # If the overall character counts don't match, rearrangement is impossible, regardless of positions.
    if Counter(string1) != Counter(string2):
        return False

    string1_even_chars = []
    string1_odd_chars = []
    for index, character in enumerate(string1):
        if index % 2 == 0:
            string1_even_chars.append(character)
        else:
            string1_odd_chars.append(character)

    string2_even_chars = []
    string2_odd_chars = []
    for index, character in enumerate(string2):
        if index % 2 == 0:
            string2_even_chars.append(character)
        else:
            string2_odd_chars.append(character)

    # Operations only allow swaps within even or odd positions, so the multiset of characters must match.
    string1_even_counts = Counter(string1_even_chars)
    string2_even_counts = Counter(string2_even_chars)
    if string1_even_counts != string2_even_counts:
        return False

    # Similarly, the characters in odd positions must be the same between the two strings.
    string1_odd_counts = Counter(string1_odd_chars)
    string2_odd_counts = Counter(string2_odd_chars)
    if string1_odd_counts != string2_odd_counts:
        return False

    return True

Big(O) Analysis

Time Complexity

O(n) – The full-string counts read each character once. Splitting even and odd positions reads each character once more. Counting a half-length list is linear in that half, so both halves together are linear in n. Comparing counts touches each distinct letter a constant number of times, and there are at most n distinct letters. All of that work is O(n).

Space Complexity

O(n) – The four position lists together store two copies of the characters, which is linear in n. The count maps hold one entry per distinct letter and are bounded by the alphabet or by n, whichever is smaller. No permutation lists are retained. A few loop indexes are constant. Extra space is O(n).

Edge Cases

Case	How to Handle
The strings have different lengths	Return false immediately, because swaps cannot change how long a string is.
The overall multiset of letters differs	Return false before position checks, because swaps cannot create or remove a letter.
Even positions match and odd positions do not	Return false when the odd-position letter counts disagree.
The string has a single character	Return true only when that character matches, since there is no second index to swap.
Duplicate letters would repeat the same arrangement many times	Store each distinct arrangement once before testing it against the target.
Both the even counts and the odd counts match	Return true, because each of those two groups can be reordered freely.

The strings have different lengths

How to Handle:

Return false immediately, because swaps cannot change how long a string is.

The overall multiset of letters differs

How to Handle:

Return false before position checks, because swaps cannot create or remove a letter.

Even positions match and odd positions do not

How to Handle:

Return false when the odd-position letter counts disagree.

The string has a single character

How to Handle:

Return true only when that character matches, since there is no second index to swap.

Duplicate letters would repeat the same arrangement many times

How to Handle:

Store each distinct arrangement once before testing it against the target.

Both the even counts and the odd counts match

How to Handle:

Return true, because each of those two groups can be reordered freely.