Pages

15/07/2021

[Java] Buddy strings

Given two strings, check whether exactly ONE swap of two different characters can be made in any string to form the other.

Example:

abc,abc: false

asd,jkl: false

aa,aa: true

ab,ab: false

ab,ba: true

The main issue is that we FORCE a swap, even if strings are equal already.

After checking for string length which must be at least 2 and both must have same length, we can walk both strings at the same time, counting number or unmatched characters. 

If we ever have more than 2 mismatched characters, we stop and return false as we can only swap two characters at most (eg: asd,jkl), otherwise we track the indices of the mismatched ones.
 

Also we check if a string has any duplicate characters, this is necessary as we MUST perform a swap, even if the strings are equal. Therefore we need to have the possibility to do a harmless swap between two duplicates (eg: aa,aa is ok but ab,ab is not).
 

At the end we have the following cases:

  • no unmatched chars found: we must force a swap between duplicates, if there are any
  • one unmatched char found: we cannot swap it with anything
  • exactly two unmatched chars found: we need to verify whether the two strings have matching chars at the inverted indices so we can swap them

This will work in O(N) time and space.

You can check my implementation of checkBuddyStrings on my Gist along with some tests in CheckBuddyStringsJTests.

No comments:

Post a Comment

With great power comes great responsibility