Skip to content

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:

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 * 104
  • s and goal consist of lowercase letters.

Solutions

Solution 1

Thinking

We must swap exactly two characters of \(s\) to obtain \(\textit{goal}\). Different lengths or different letter counts are impossible. \(n\le 2\cdot 10^4\), so one scan of mismatch positions is enough.

Exactly two mismatches work because the counts already match. A fully equal pair needs some letter appearing twice, so a no-op swap exists.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        m, n = len(s), len(goal)
        if m != n:
            return False
        cnt1, cnt2 = Counter(s), Counter(goal)
        if cnt1 != cnt2:
            return False
        diff = sum(s[i] != goal[i] for i in range(n))
        return diff == 2 or (diff == 0 and any(v > 1 for v in cnt1.values()))

 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
class Solution {
    public boolean buddyStrings(String s, String goal) {
        int m = s.length(), n = goal.length();
        if (m != n) {
            return false;
        }
        int diff = 0;
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        for (int i = 0; i < n; ++i) {
            int a = s.charAt(i), b = goal.charAt(i);
            ++cnt1[a - 'a'];
            ++cnt2[b - 'a'];
            if (a != b) {
                ++diff;
            }
        }
        boolean f = false;
        for (int i = 0; i < 26; ++i) {
            if (cnt1[i] != cnt2[i]) {
                return false;
            }
            if (cnt1[i] > 1) {
                f = true;
            }
        }
        return diff == 2 || (diff == 0 && f);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool buddyStrings(string s, string goal) {
        int m = s.size(), n = goal.size();
        if (m != n) return false;
        int diff = 0;
        vector<int> cnt1(26);
        vector<int> cnt2(26);
        for (int i = 0; i < n; ++i) {
            ++cnt1[s[i] - 'a'];
            ++cnt2[goal[i] - 'a'];
            if (s[i] != goal[i]) ++diff;
        }
        bool f = false;
        for (int i = 0; i < 26; ++i) {
            if (cnt1[i] != cnt2[i]) return false;
            if (cnt1[i] > 1) f = true;
        }
        return diff == 2 || (diff == 0 && f);
    }
};

 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
func buddyStrings(s string, goal string) bool {
    m, n := len(s), len(goal)
    if m != n {
        return false
    }
    diff := 0
    cnt1 := make([]int, 26)
    cnt2 := make([]int, 26)
    for i := 0; i < n; i++ {
        cnt1[s[i]-'a']++
        cnt2[goal[i]-'a']++
        if s[i] != goal[i] {
            diff++
        }
    }
    f := false
    for i := 0; i < 26; i++ {
        if cnt1[i] != cnt2[i] {
            return false
        }
        if cnt1[i] > 1 {
            f = true
        }
    }
    return diff == 2 || (diff == 0 && f)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function buddyStrings(s: string, goal: string): boolean {
    const m = s.length;
    const n = goal.length;
    if (m != n) {
        return false;
    }
    const cnt1 = new Array(26).fill(0);
    const cnt2 = new Array(26).fill(0);
    let diff = 0;
    for (let i = 0; i < n; ++i) {
        cnt1[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
        cnt2[goal.charCodeAt(i) - 'a'.charCodeAt(0)]++;
        if (s[i] != goal[i]) {
            ++diff;
        }
    }
    for (let i = 0; i < 26; ++i) {
        if (cnt1[i] != cnt2[i]) {
            return false;
        }
    }
    return diff == 2 || (diff == 0 && cnt1.some(v => v > 1));
}

Comments