Scale Engineer

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 TableString
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 <= 105
  • 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.

import java.util.Arrays; class Solution {    public boolean checkStrings(String s1, String s2) {        int n = s1.length();        StringBuilder s1Even = new StringBuilder();        StringBuilder s1Odd = new StringBuilder();        StringBuilder s2Even = new StringBuilder();        StringBuilder s2Odd = new StringBuilder();         for (int i = 0; i < n; i++) {            if (i % 2 == 0) {                s1Even.append(s1.charAt(i));                s2Even.append(s2.charAt(i));            } else {                s1Odd.append(s1.charAt(i));                s2Odd.append(s2.charAt(i));            }        }         char[] s1EvenChars = s1Even.toString().toCharArray();        char[] s2EvenChars = s2Even.toString().toCharArray();        Arrays.sort(s1EvenChars);        Arrays.sort(s2EvenChars);         char[] s1OddChars = s1Odd.toString().toCharArray();        char[] s2OddChars = s2Odd.toString().toCharArray();        Arrays.sort(s1OddChars);        Arrays.sort(s2OddChars);         return Arrays.equals(s1EvenChars, s2EvenChars) && Arrays.equals(s1OddChars, s2OddChars);    }}

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.

Solutions

class Solution {public  boolean checkStrings(String s1, String s2) {    int[][] cnt = new int[2][26];    for (int i = 0; i < s1.length(); ++i) {      ++cnt[i & 1][s1.charAt(i) - 'a'];      --cnt[i & 1][s2.charAt(i) - 'a'];    }    for (int i = 0; i < 26; ++i) {      if (cnt[0][i] != 0 || cnt[1][i] != 0) {        return false;      }    }    return true;  }}

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 →

Next problem