859. Buddy Strings

2023, Mar 05 2 mins read

1. 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”.

2. Example

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.

3. Constraints

1 <= s.length, goal.length <= $2 * 10^4$
s and goal consist of lowercase letters.

4. Solutions

Hash Table

n = str.size()
Time complexity: O(n)
Space complexity: O(1)

 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
40
41
class Solution {
public:
    bool buddyStrings(const string &str, const string &goal) {
        if (str.size() != goal.size()) {
            return false;
        }

        array<int, 26> letter_diff{0};
        bool duplicate_letter = false;
        for (int i = 0; i < str.size(); ++i) {
            ++letter_diff[get_index_(str[i])];
            --letter_diff[get_index_(goal[i])];
        }
        for (int i = 0; i < 26; ++i) {
            if (letter_diff[i] != 0) {
                return false;
            }
        }

        int letter_diff_count = 0;
        array<int, 26> letter_count{0};
        bool has_duplicate_letter = false;
        for (int i = 0; i < str.size(); ++i) {
            ++letter_diff[get_index_(str[i])];
            if (letter_diff[get_index_(str[i])] > 1) {
                has_duplicate_letter = true;
            }

            if (str[i] != goal[i]) {
                ++letter_diff_count;
            }
        }

        return letter_diff_count == 0 && has_duplicate_letter || letter_diff_count == 2;
    }

private:
    inline int get_index_(char letter) {
        return letter - 'a';
    }
};

Search

Tags