Skip to content

859. Buddy Strings

  • Time: $O(n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  bool buddyStrings(string s, string goal) {
    if (s.length() != goal.length())
      return false;
    if (s == goal && hasDuplicateLetters(s))
      return true;

    vector<int> diffIndices;

    for (int i = 0; i < s.length(); ++i)
      if (s[i] != goal[i])
        diffIndices.push_back(i);

    return diffIndices.size() == 2 &&
           s[diffIndices[0]] == goal[diffIndices[1]] &&
           s[diffIndices[1]] == goal[diffIndices[0]];
  }

 private:
  bool hasDuplicateLetters(const string& s) {
    vector<int> count(26);
    for (const char c : s)
      ++count[c - 'a'];
    return ranges::any_of(count, [](int freq) { return freq > 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
class Solution {
  public boolean buddyStrings(String s, String goal) {
    if (s.length() != goal.length())
      return false;
    if (s.equals(goal) && hasDuplicateLetters(s))
      return true;

    List<Integer> diffIndices = new ArrayList<>();

    for (int i = 0; i < s.length(); ++i)
      if (s.charAt(i) != goal.charAt(i))
        diffIndices.add(i);

    return diffIndices.size() == 2 &&
        s.charAt(diffIndices.get(0)) == goal.charAt(diffIndices.get(1)) &&
        s.charAt(diffIndices.get(1)) == goal.charAt(diffIndices.get(0));
  }

  private boolean hasDuplicateLetters(String s) {
    int[] count = new int[26];
    for (char c : s.toCharArray())
      ++count[c - 'a'];
    return Arrays.stream(count).anyMatch(freq -> freq > 1);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def buddyStrings(self, s: str, goal: str) -> bool:
    if len(s) != len(goal):
      return False
    if s == goal and len(set(s)) < len(s):
      return True
    diffIndices = [i for i, (a, b) in enumerate(zip(s, goal))
                   if a != b]
    return (len(diffIndices) == 2 and
            s[diffIndices[0]] == goal[diffIndices[1]] and
            s[diffIndices[1]] == goal[diffIndices[0]])