859. Buddy Strings

Posted on Edited on In

859. Buddy Strings

Description

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].

  • For example, swapping at indices 0 and 2 in "abcd" results in "cbad".

Example 1:

1
2
3
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:

1
2
3
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:

1
2
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 * 10^4
  • s and goal consist of lowercase letters.

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    bool buddyStrings(string s, string goal) {
        int n = s.size();
        if (goal.size() != n) {
            return false;
        }
        if (s == goal) {
            int count[26]{};
            for (int i = 0; i < n; i++) {
                count[s[i] - 'a']++;
                if (count[s[i] - 'a'] > 1) {
                    return true;
                }
            }
            return false;
        } else {
            int prev = -1;
            bool found = false;
            for (int i = 0; i < n; i++) {
                if (s[i] != goal[i]) {
                    if (found) {
                        return false;
                    }
                    if (prev == -1) {
                        prev = i;
                    } else {
                        if (s[prev] == goal[i] && s[i] == goal[prev]) {
                            found = true;
                        } else {
                            return false;
                        }
                    }
                }
            }
            return found;
        }
    }
};