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:
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.length1 <= n <= 105s1 and s2 consist only of lowercase English letters.This approach involves splitting each string into two separate lists: one containing characters at even indices and the other containing characters at odd indices. This works because you can only swap characters within each group, i.e., even or odd indexed characters.
If the characters present at the even indices of s1 can be rearranged to match the characters at the even indices of s2, and similarly for the characters at the odd indices, then it's possible to make s1 equal to s2.
The C solution manually sorts the characters at even and odd indices separately for both strings s1 and s2 using simple selection sort, and then compares the sorted strings.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), Space Complexity: O(1)
This approach focuses on character frequencies at even and odd indices. We can make two strings equal by matching the frequency of each character at even indices independently of odd indices because any even index can swap with another even index, and the same goes for odd indices.
Set up two frequency arrays (or hash maps) to count the occurrences of each character at even indices and odd indices in both strings and compare them to check if they are equivalent across both strings.
The C solution uses two frequency arrays to count character occurrences at even and odd indices. It increments the counts for s1 and decrements for s2, and checks whether both frequency lists are zero.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Approach One: Separate Even and Odd Indexed Characters | Time Complexity: O(n^2), Space Complexity: O(1) |
| Approach Two: Character Frequency Matching for Even and Odd Positions | Time Complexity: O(n), Space Complexity: O(1) |
Check if One String Swap Can Make Strings Equal - Leetcode 1790 - Python • NeetCodeIO • 7,298 views views
Watch 9 more video solutions →Practice Check if Strings Can be Made Equal With Operations II with our built-in code editor and test cases.
Practice on FleetCode