Buddy Strings

Problem

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".

Examples

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.

Solution

his problem involves checking whether two strings, s and goal, can be made equal by swapping exactly two characters in s.

Method 1 - Using counts array

Here is how we can solve this problem:

1. Length Check: First, check if the lengths of the two strings are different. If they are, return false because it's impossible to make them equal through any number of swaps.
2. Immediate Match: If the two strings are already equal, check if there are at least two duplicate characters in s. This would allow us to swap two identical characters in s, thereby preserving its equality with goal.
3. Identify Swap Position: If the strings are not equal, identify the positions where the characters differ. If there are exactly two differences, check if swapping these two characters in s makes it equal to goal.
4. Conclusion: Return true if the conditions are met, otherwise return false.

Code

Java

public class Solution {

	public boolean buddyStrings(String s, String goal) {
		if (s.length() != goal.length()) {
			return false;
		}

		if (s.equals(goal)) {
			// Check if there is at least one character that appears twice
			int[] count = new int[26];

			for (char c: s.toCharArray()) {
				count[c - 'a']++;

				if (count[c - 'a'] > 1) {
					return true;
				}
			}

			return false;
		}

		int first = -1, second = -1;

		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) != goal.charAt(i)) {
				if (first == -1) {
					first = i;
				} else if (second == -1) {
					second = i;
				} else {
					// More than two differences
					return false;
				}
			}
		}

		return (second != -1 &&
			s.charAt(first) == goal.charAt(second) &&
			s.charAt(second) == goal.charAt(first));
	}

}

Complexity

• ⏰ Time complexity: O(n), where n is length of goal string.
• 🧺 Space complexity: O(26)

Method 2 - Using set

Code

Java

public class Solution {

	public boolean buddyStrings(String s, String goal) {
		if (s.length() != goal.length()) {
			return false;
		}

		if (s.equals(goal)) {
			// Check if there is at least one character that appears twice
			Set<Character> sChars = new HashSet<>();

			for (char c: s.toCharArray()) {
				if (!sChars.add(c)) {
					return true;
				}
			}

			return false;
		}

		int first = -1, second = -1;

		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) != goal.charAt(i)) {
				if (first == -1) {
					first = i;
				} else if (second == -1) {
					second = i;
				} else {
					// More than two differences
					return false;
				}
			}
		}

		return (second != -1 &&
			s.charAt(first) == goal.charAt(second) &&
			s.charAt(second) == goal.charAt(first));
	}

}

Method 3 - One pass

Code

Java

public class Solution {

	public boolean buddyStrings(String s, String goal) {
		if (s.length() != goal.length()) {
			return false;
		}
		Set<Character> sChars = new HashSet<>();

		int first = -1, second = -1;

		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			char d = goal.charAt(i);
			if (c != d) {
				if (first == -1) {
					first = i;
				} else if (second == -1) {
					second = i;
				} else {
					// More than two differences
					return false;
				}
			}
			sChars.add(c);
		}

		if (first != -1 && second != -1) {
			return s.charAt(first) == goal.charAt(second) &&
			s.charAt(second) == goal.charAt(first));
		}
		if (first != -1) {
			return false;  // Only have 1 different place
		}
		return sChars.size() < s.length(); // No different between s & goal, check if A contains at least 1 duplicate letters.
	}

}