Leetcode[859] Buddy Strings

Constraints

  • 0 <= A.length <= 20000
  • 0 <= B.length <= 20000
  • A and B consist of lowercase letters.

Difficulty

  • Level: Easy
  • Acceptance: 29.5%

Solution

Time Complexity: O(n), Space Complexity: O(n)

Analysis

For this problem, one of the challenging parts was finding all the possible cases of success and failure for the algorithm. After some trial and error, it can be boiled down to these 3:

  • If both strings are equal, check to see if there is a duplication in one of the letters. If so, you can swap them together as swapping two characters within the string is a must. And in doing so, will still yield the same string and return true. I used a set to keep track of unique characters.
  • If both strings are unequal to each other, loop through them and find character pairs from A and B that are not the same and add them to an array. The strings are only “buddy strings” and true if there are exactly 4 characters in the array and the concatenation of the third and first character(from A) is the same as the concatenation of the second and last character(from B). This simulates the swap of just 2 characters in A.

I have a passion for coding.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store