Jobs

Interviews

Discussions

Check if Strings Can be Made Equal With Operations I

Easy

Asked by:

7 views

Topics:

Strings

You are given two strings s1 and s2, both of length 4, 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 j - i = 2, 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 = "abcd", s2 = "cdab"
Output: true
Explanation: We can do the following operations on s1:
- Choose the indices i = 0, j = 2. The resulting string is s1 = "cbad".
- Choose the indices i = 1, j = 3. The resulting string is s1 = "cdab" = s2.

Example 2:

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

Constraints:

s1.length == s2.length == 4
s1 and s2 consist only of lowercase English letters.

Try coding it in LeetCode

Check if Strings Can be Made Equal With Operations I

Easy

Asked by:

7 views

Topics:

Strings

You are given two strings s1 and s2, both of length 4, 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 j - i = 2, 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 = "abcd", s2 = "cdab"
Output: true
Explanation: We can do the following operations on s1:
- Choose the indices i = 0, j = 2. The resulting string is s1 = "cbad".
- Choose the indices i = 1, j = 3. The resulting string is s1 = "cdab" = s2.

Example 2:

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

Constraints:

s1.length == s2.length == 4
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:

Is each string exactly four characters, so the only distance-two pairs are the first with the third and the second with the fourth?
Can a pair be swapped more than once, which would put those characters back?
Is it enough to rearrange one string, because the same swaps could be applied to the other?
Do these swaps keep even positions from mixing with odd positions?
Should two strings that are already equal succeed without a swap?

Brute Force Solution

Approach

This check tries the arrangements reachable by swapping the first character with the third, the second with the fourth, or both. It compares the original text first, then each of those three swapped forms. It returns true on the first match and false when all four forms miss the target.

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

Return true immediately when the two strings are already the same.
Copy the first string into a mutable list of characters.
Swap the first and third characters and return true if the list now matches the target.
Swap that pair back so the list is original again.
Swap the second and fourth characters and return true on a match.
Swap the first and third characters as well, so both pairs are exchanged, and test again.
Return false when that last arrangement still differs from the target.

Code Implementation

class Solution:
    def canBeEqual(self, first_string: str, second_string: str) -> bool:
        # Check if the strings are already identical without any operations.
        if first_string == second_string:
            return True

        first_string_as_list = list(first_string)

        # Perform the first possible swap: exchange characters at indices 0 and 2.
        first_string_as_list[0], first_string_as_list[2] = first_string_as_list[2], first_string_as_list[0]
        if "".join(first_string_as_list) == second_string:
            return True

        # Undo the swap to revert to the original state for the next check.
        first_string_as_list[0], first_string_as_list[2] = first_string_as_list[2], first_string_as_list[0]

        # Perform the second possible swap: exchange characters at indices 1 and 3.
        first_string_as_list[1], first_string_as_list[3] = first_string_as_list[3], first_string_as_list[1]
        if "".join(first_string_as_list) == second_string:
            return True

        # Now, try both swaps together. The second swap is already applied, so just apply the first.
        first_string_as_list[0], first_string_as_list[2] = first_string_as_list[2], first_string_as_list[0]
        if "".join(first_string_as_list) == second_string:
            return True

        return False

Big(O) Analysis

Time Complexity

O(1) – The strings have a fixed length of four, so every comparison looks at a constant number of characters. There are only two distance-two pairs, and the procedure tries a constant number of arrangements of those pairs. Each swap touches two positions. No loop grows with a variable input size. The work is O(1).

Space Complexity

O(1) – The mutable copy holds four characters, which does not grow. The comparisons build a four-character string from that copy and discard it. No collection of extra arrangements is stored. A handful of indexes is enough. Extra space is O(1).

Optimal Solution

Approach

Allowed swaps only rearrange the even positions among themselves and the odd positions among themselves. The strings can be made equal exactly when those two pairs of positions carry the same letters with the same counts. The check therefore compares the even-position multiset and the odd-position multiset.

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

Collect the characters sitting on even indexes in each string.
Collect the characters sitting on odd indexes in each string.
Compare the counts of the two even collections.
Return false when any letter count in the even collections differs.
Compare the counts of the two odd collections.
Return false when any letter count in the odd collections differs.
Return true when both pairs of collections match.

Code Implementation

from collections import Counter

class Solution:
    def canBeEqual(self, first_string: str, second_string: str) -> bool:
        # Step 1 & 2: Segregate characters from both strings into even and odd indexed groups.
        # This separation is crucial because the allowed operations only permit swaps within these groups.
        first_string_even_chars = first_string[0::2]
        first_string_odd_chars = first_string[1::2]
        second_string_even_chars = second_string[0::2]
        second_string_odd_chars = second_string[1::2]

        # Step 3: Compare the character counts for the even-indexed positions.
        # The order doesn't matter, only that the same multiset of characters exists.
        if Counter(first_string_even_chars) != Counter(second_string_even_chars):
            return False

        # Step 4: Similarly, compare the character counts for the odd-indexed positions.
        # This ensures the odd positions can also be rearranged to match.
        if Counter(first_string_odd_chars) != Counter(second_string_odd_chars):
            return False

        # Step 5: If both even and odd character sets match, the strings can be made equal.
        return True

Big(O) Analysis

Time Complexity

O(n) – Slicing out the even positions and the odd positions reads every character a constant number of times. Building a count for a slice is proportional to the slice length, and the two slices together cover the string. Comparing two counts is proportional to the number of distinct letters, which is bounded by the string length. The strings are the same length n, and the fixed length in this problem is four. The scan is O(n).

Space Complexity

O(n) – Each slice copies half of a string, so the four slices together hold two full copies of the characters. The counts store one entry per distinct letter in those slices. No further recursion or search memory is used. The extra copied characters scale with the string length. The space is O(n).

Edge Cases

Case	How to Handle
The strings are already equal	Return true immediately, before any swap is attempted.
Only the first and third characters need to change places	Swap that pair and return true when the text then matches the target.
Only the second and fourth characters need to change places	Undo any earlier even swap, swap the odd pair, and return true on a match.
Both pairs must change	Apply both swaps and return true when that arrangement equals the target.
The letters on even positions differ as a multiset	Return false, because no allowed swap can move a letter from an even position to an odd one.
None of the four reachable arrangements matches	Return false after the original text and the three swapped forms have all failed.

The strings are already equal

How to Handle:

Return true immediately, before any swap is attempted.

Only the first and third characters need to change places

How to Handle:

Swap that pair and return true when the text then matches the target.

Only the second and fourth characters need to change places

How to Handle:

Undo any earlier even swap, swap the odd pair, and return true on a match.

Both pairs must change

How to Handle:

Apply both swaps and return true when that arrangement equals the target.

The letters on even positions differ as a multiset

How to Handle:

Return false, because no allowed swap can move a letter from an even position to an odd one.

None of the four reachable arrangements matches

How to Handle:

Return false after the original text and the three swapped forms have all failed.

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:

Is each string exactly four characters, so the only distance-two pairs are the first with the third and the second with the fourth?
Can a pair be swapped more than once, which would put those characters back?
Is it enough to rearrange one string, because the same swaps could be applied to the other?
Do these swaps keep even positions from mixing with odd positions?
Should two strings that are already equal succeed without a swap?

Brute Force Solution

Approach

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

Return true immediately when the two strings are already the same.
Copy the first string into a mutable list of characters.
Swap the first and third characters and return true if the list now matches the target.
Swap that pair back so the list is original again.
Swap the second and fourth characters and return true on a match.
Swap the first and third characters as well, so both pairs are exchanged, and test again.
Return false when that last arrangement still differs from the target.

Code Implementation

class Solution:
    def canBeEqual(self, first_string: str, second_string: str) -> bool:
        # Check if the strings are already identical without any operations.
        if first_string == second_string:
            return True

        first_string_as_list = list(first_string)

        # Perform the first possible swap: exchange characters at indices 0 and 2.
        first_string_as_list[0], first_string_as_list[2] = first_string_as_list[2], first_string_as_list[0]
        if "".join(first_string_as_list) == second_string:
            return True

        # Undo the swap to revert to the original state for the next check.
        first_string_as_list[0], first_string_as_list[2] = first_string_as_list[2], first_string_as_list[0]

        # Perform the second possible swap: exchange characters at indices 1 and 3.
        first_string_as_list[1], first_string_as_list[3] = first_string_as_list[3], first_string_as_list[1]
        if "".join(first_string_as_list) == second_string:
            return True

        # Now, try both swaps together. The second swap is already applied, so just apply the first.
        first_string_as_list[0], first_string_as_list[2] = first_string_as_list[2], first_string_as_list[0]
        if "".join(first_string_as_list) == second_string:
            return True

        return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Collect the characters sitting on even indexes in each string.
Collect the characters sitting on odd indexes in each string.
Compare the counts of the two even collections.
Return false when any letter count in the even collections differs.
Compare the counts of the two odd collections.
Return false when any letter count in the odd collections differs.
Return true when both pairs of collections match.

Code Implementation

from collections import Counter

class Solution:
    def canBeEqual(self, first_string: str, second_string: str) -> bool:
        # Step 1 & 2: Segregate characters from both strings into even and odd indexed groups.
        # This separation is crucial because the allowed operations only permit swaps within these groups.
        first_string_even_chars = first_string[0::2]
        first_string_odd_chars = first_string[1::2]
        second_string_even_chars = second_string[0::2]
        second_string_odd_chars = second_string[1::2]

        # Step 3: Compare the character counts for the even-indexed positions.
        # The order doesn't matter, only that the same multiset of characters exists.
        if Counter(first_string_even_chars) != Counter(second_string_even_chars):
            return False

        # Step 4: Similarly, compare the character counts for the odd-indexed positions.
        # This ensures the odd positions can also be rearranged to match.
        if Counter(first_string_odd_chars) != Counter(second_string_odd_chars):
            return False

        # Step 5: If both even and odd character sets match, the strings can be made equal.
        return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
The strings are already equal	Return true immediately, before any swap is attempted.
Only the first and third characters need to change places	Swap that pair and return true when the text then matches the target.
Only the second and fourth characters need to change places	Undo any earlier even swap, swap the odd pair, and return true on a match.
Both pairs must change	Apply both swaps and return true when that arrangement equals the target.
The letters on even positions differ as a multiset	Return false, because no allowed swap can move a letter from an even position to an odd one.
None of the four reachable arrangements matches	Return false after the original text and the three swapped forms have all failed.

The strings are already equal

How to Handle:

Return true immediately, before any swap is attempted.

Only the first and third characters need to change places

How to Handle:

Swap that pair and return true when the text then matches the target.

Only the second and fourth characters need to change places

How to Handle:

Undo any earlier even swap, swap the odd pair, and return true on a match.

Both pairs must change

How to Handle:

Apply both swaps and return true when that arrangement equals the target.

The letters on even positions differ as a multiset

How to Handle:

Return false, because no allowed swap can move a letter from an even position to an odd one.

None of the four reachable arrangements matches

How to Handle:

Return false after the original text and the three swapped forms have all failed.