Given two strings s and goal, return true if you can swap two letters in s so the result is equal to goal, otherwise, return false.
Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at s[i] and s[j].
0 and 2 in "abcd" results in "cbad".
Example 1:
Input: s = "ab", goal = "ba" Output: true Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.
Example 2:
Input: s = "ab", goal = "ab" Output: false Explanation: The only letters you can swap are s[0] = 'a' and s[1] = 'b', which results in "ba" != goal.
Example 3:
Input: s = "aa", goal = "aa" Output: true Explanation: You can swap s[0] = 'a' and s[1] = 'a' to get "aa", which is equal to goal.
Constraints:
1 <= s.length, goal.length <= 2 * 104s and goal consist of lowercase letters.This approach involves a straightforward comparison between the two strings. First, check if both strings are equal in length. If not, return false immediately. Next, identify the indices where the two strings differ. If there are exactly two such indices and swapping these characters in the first string can make it identical to the second, return true. Additionally, handle the edge case where both strings are already identical but contain at least one character that repeats, in which case a swap is possible and returns true.
The function first checks if the strings are of different lengths, returning false immediately. It then handles the case when both strings are identical by checking for repeated characters using a set, since a swap is impossible without repetition. For differing strings, it constructs a list of differing positions. If there are exactly two differences and swapping them resolves equality, the function returns true.
JavaScript
Time Complexity: O(n), as we traverse the strings with a single pass to gather differences.
Space Complexity: O(1) for constant-space operations, though storing differences requires space proportional to the number of differences.
This alternative method relies on character frequency counts and permutation verifications. If the strings differ in length, they're immediately ruled out. By evaluating how character frequencies align and applying permutation checks, the function can discern valid swaps that potentially achieve the goal formation of the strings.
The Java Solution uses ArrayList to store differing indices while also handling special cases for direct equality and duplication presence. It'll iterate through the string, populating discrepancies only to check their viability for a simple swap.
C#
Time Complexity: O(n), scanning all potential indices to locate and evaluate differences.
Space Complexity: O(n) theoretically with list storage though practically controlled by processing mechanism constraints.
| Approach | Complexity |
|---|---|
| Direct Comparison with Character Swapping | Time Complexity: O(n), as we traverse the strings with a single pass to gather differences. |
| Character Frequency and Permutation Check | Time Complexity: O(n), scanning all potential indices to locate and evaluate differences. |
LeetCode Buddy Strings Solution Explained - Java • Nick White • 11,179 views views
Watch 9 more video solutions →Practice Buddy Strings with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor