Check if Strings Can be Made Equal With Operations II

Med

#2539Time: O(N log N), where N is the length of the strings. The dominant operation is sorting the subsequences. The length of each subsequence is approximately N/2, so sorting takes O((N/2) log(N/2)), which simplifies to O(N log N).Space: O(N), where N is the length of the strings. We need to store the four subsequences, each of length approximately N/2. This results in a total space complexity proportional to N.1 company

Algorithms

Sorting

Data structures

Hash Table String

Companies

Citrix

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach is based on the key insight that the operation allows any permutation of characters at even indices among themselves, and any permutation of characters at odd indices among themselves. Therefore, two strings can be made equal if and only if the multiset of characters at their even indices are identical, and the multiset of characters at their odd indices are also identical. A straightforward way to check if two multisets are identical is to sort them and compare the resulting sequences.

Algorithm

Create four StringBuilders: s1_even, s1_odd, s2_even, and s2_odd.
Iterate through the input strings s1 and s2 from index i = 0 to n-1.
If i is even, append s1.charAt(i) to s1_even and s2.charAt(i) to s2_even.
If i is odd, append s1.charAt(i) to s1_odd and s2.charAt(i) to s2_odd.
Convert the four StringBuilders to character arrays.
Sort the character arrays corresponding to the even indices (s1_even, s2_even).
Sort the character arrays corresponding to the odd indices (s1_odd, s2_odd).
Compare the sorted even-indexed arrays and the sorted odd-indexed arrays. If both pairs are equal, return true. Otherwise, return false.

Walkthrough

The algorithm first separates the characters of each string into two groups: those at even indices and those at odd indices. This is done by iterating through each string and appending characters to the appropriate StringBuilder. After separating the characters, we have four subsequences: s1_even, s1_odd, s2_even, and s2_odd. To check if the multisets of characters are the same, we convert these subsequences into character arrays and sort them. If the sorted array of even-indexed characters from s1 is identical to that from s2, and the same holds for the odd-indexed characters, it means the strings can be made equal.

1import java.util.Arrays;2 3class Solution {4    public boolean checkStrings(String s1, String s2) {5        int n = s1.length();6        StringBuilder s1Even = new StringBuilder();7        StringBuilder s1Odd = new StringBuilder();8        StringBuilder s2Even = new StringBuilder();9        StringBuilder s2Odd = new StringBuilder();10 11        for (int i = 0; i < n; i++) {12            if (i % 2 == 0) {13                s1Even.append(s1.charAt(i));14                s2Even.append(s2.charAt(i));15            } else {16                s1Odd.append(s1.charAt(i));17                s2Odd.append(s2.charAt(i));18            }19        }20 21        char[] s1EvenChars = s1Even.toString().toCharArray();22        char[] s2EvenChars = s2Even.toString().toCharArray();23        Arrays.sort(s1EvenChars);24        Arrays.sort(s2EvenChars);25 26        char[] s1OddChars = s1Odd.toString().toCharArray();27        char[] s2OddChars = s2Odd.toString().toCharArray();28        Arrays.sort(s1OddChars);29        Arrays.sort(s2OddChars);30 31        return Arrays.equals(s1EvenChars, s2EvenChars) && Arrays.equals(s1OddChars, s2OddChars);32    }33}

Complexity

Time

O(N log N), where N is the length of the strings. The dominant operation is sorting the subsequences. The length of each subsequence is approximately N/2, so sorting takes O((N/2) log(N/2)), which simplifies to O(N log N).

Space

O(N), where N is the length of the strings. We need to store the four subsequences, each of length approximately N/2. This results in a total space complexity proportional to N.

Trade-offs

Pros

Conceptually simple and easy to understand.
Directly implements the idea of checking multiset equality.

Cons

Sub-optimal time complexity due to the sorting step.
Requires extra space proportional to the input string length, which can be significant for large inputs.

This approach improves upon the sorting method by using frequency counting, which is more efficient for checking multiset equality when the alphabet size is small and fixed. Instead of sorting, we count the occurrences of each character for the even and odd indexed subsequences. By using a clever trick of incrementing counts for s1 and decrementing for s2 in a single pass, we can determine if the character distributions match with optimal time and space complexity.

Algorithm

Create two integer arrays, evenCounts and oddCounts, each of size 26, to store frequency differences. Initialize them to all zeros.
Iterate through the strings from i = 0 to n-1 in a single loop.
If index i is even, increment the count for s1.charAt(i) in evenCounts and decrement the count for s2.charAt(i) in the same array.
If index i is odd, perform the same increment/decrement operations on the oddCounts array.
After the loop, iterate through both evenCounts and oddCounts arrays. If any element is not zero, it means the character frequencies do not match, so return false.
If both arrays contain only zeros, return true.

Walkthrough

The core idea remains that the multiset of characters at even indices must match, and the same for odd indices. We use two arrays of size 26, one for even-indexed characters and one for odd-indexed, to track the balance of characters between s1 and s2. We iterate through both strings simultaneously. For each character in s1, we increment its count in the corresponding array (even/odd), and for each character in s2, we decrement its count. If, at the end, both strings have the same character distribution for even and odd positions, all counts in our frequency arrays will cancel out and become zero. A final check of the arrays confirms this. If any count is non-zero, the strings cannot be made equal.

1class Solution {2    public boolean checkStrings(String s1, String s2) {3        int n = s1.length();4        int[] evenCounts = new int[26];5        int[] oddCounts = new int[26];6 7        for (int i = 0; i < n; i++) {8            if (i % 2 == 0) {9                evenCounts[s1.charAt(i) - 'a']++;10                evenCounts[s2.charAt(i) - 'a']--;11            } else {12                oddCounts[s1.charAt(i) - 'a']++;13                oddCounts[s2.charAt(i) - 'a']--;14            }15        }16 17        for (int i = 0; i < 26; i++) {18            if (evenCounts[i] != 0 || oddCounts[i] != 0) {19                return false;20            }21        }22 23        return true;24    }25}

Complexity

Time

O(N), where N is the length of the strings. We perform a single pass through the strings of length N, and then two constant-time loops of size 26. The overall complexity is dominated by the first loop.

Space

O(1). We use two arrays of a fixed size (26) to store the character counts. The space required does not depend on the input string length N, making it constant.

Trade-offs

Pros

Optimal time complexity of O(N).
Optimal space complexity of O(1).
Efficient in practice due to a single pass and array-based operations.

Cons

Slightly less direct than the sorting approach, as it relies on the frequency counting trick.

Solutions

Solution

1class Solution {2public3  boolean checkStrings(String s1, String s2) {4    int[][] cnt = new int[2][26];5    for (int i = 0; i < s1.length(); ++i) {6      ++cnt[i & 1][s1.charAt(i) - 'a'];7      --cnt[i & 1][s2.charAt(i) - 'a'];8    }9    for (int i = 0; i < 26; ++i) {10      if (cnt[0][i] != 0 || cnt[1][i] != 0) {11        return false;12      }13    }14    return true;15  }16}

1class Solution {2public:3  bool checkStrings(string s1, string s2) {4    vector<vector<int>> cnt(2, vector<int>(26, 0));5    for (int i = 0; i < s1.size(); ++i) {6      ++cnt[i & 1][s1[i] - 'a'];7      --cnt[i & 1][s2[i] - 'a'];8    }9    for (int i = 0; i < 26; ++i) {10      if (cnt[0][i] || cnt[1][i]) {11        return false;12      }13    }14    return true;15  }16};

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem