#2840

Medium

LeetCode Problem Workspace

Check if Strings Can be Made Equal With Operations II

Check if two strings can be made equal using operations that swap characters with the same parity.

Problem Statement

You are given two strings, s1 and s2, each of length n, composed of lowercase English letters. The goal is to determine if these strings can be made equal by performing a specific swap operation any number of times.

The operation allows you to swap characters between two positions in the string if and only if both positions have the same parity (both even or both odd). You need to return true if s1 and s2 can be made equal with these operations, and false otherwise.

Examples

Example 1

Input: s1 = "abcdba", s2 = "cabdab"

Output: true

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

It is not possible to make the two strings equal.

Constraints

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

Solution Approach

Check Character Frequencies

Start by ensuring that both strings have identical character frequencies at even and odd indices. The parity of character positions is crucial to this check, as swaps can only occur between characters at positions with matching parity.

Use Hashing for Efficient Comparison

Leverage hash tables to track the frequency of characters at even and odd positions in both strings. This allows you to efficiently compare the character distributions in both strings and identify if they can be made equal through allowed swaps.

Match Parity Indices

Ensure that for each string, characters in positions with the same parity (odd/even) match between s1 and s2. If the characters at these corresponding positions are not the same, return false.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) due to the single pass required to count characters in each string, where n is the length of the strings. Space complexity is O(n) as we store the frequency counts for both even and odd positions of the strings.

What Interviewers Usually Probe

Assess whether the candidate can think through the problem with the correct pattern, focusing on parity and hashing.
Look for an understanding of string manipulation and character frequency counting for efficient solutions.
Evaluate how the candidate handles edge cases, such as strings with mismatched characters or impossible swaps.

Common Pitfalls or Variants

Common pitfalls

Forgetting to account for the parity constraint in swaps, leading to incorrect conclusions about the possibility of equalizing the strings.
Overcomplicating the problem with unnecessary operations instead of focusing on character parity and frequency.
Not considering edge cases like when the strings are already equal or contain only one character.

Follow-up variants

Introduce a condition where swaps are allowed only between characters at specific intervals or positions, testing how well the candidate adapts the solution.
Modify the problem to handle strings of varying lengths, where padding or trimming may be necessary before applying the operations.
Increase the complexity by introducing constraints on the number of swaps allowed, adding a new layer of problem-solving.

FAQ

What is the key observation in 'Check if Strings Can be Made Equal With Operations II'?

The key observation is that characters can only be swapped if they share the same parity (even or odd index positions).

How does hash table usage help solve this problem?

Hash tables efficiently track the frequency of characters at even and odd indices, enabling quick comparison between the two strings.

Can this problem be solved without considering parity constraints?

No, the problem specifically requires that swaps only occur between characters at positions with matching parity.

What is the time complexity of this problem?

The time complexity is O(n), where n is the length of the strings, due to the need to iterate through both strings once.

Are there any common mistakes to avoid in solving this problem?

Common mistakes include forgetting to check for parity constraints in swaps or overcomplicating the solution by not focusing on efficient counting methods.

terminal

Solution

Solution 1: Counting

We observe the operation in the problem, and find that if the parity of the two indices $i$ and $j$ of the string is the same, then their order can be changed by swapping.

1

2

3

4

5

class Solution:
    def checkStrings(self, s1: str, s2: str) -> bool:
        return Counter(s1[::2]) == Counter(s2[::2]) and Counter(s1[1::2]) == Counter(
            s2[1::2]
        )

Continue Practicing

#2933 high access employees #3016 minimum number of pushes to type word ii #3035 maximum palindromes after operations