algoadvance

Leetcode 859. Buddy Strings

Problem Statement

You are given two strings s and goal. Your task is to determine if you can obtain the string goal by swapping two letters in the string s.

Return true if it is possible, otherwise return false.

Example 1:

Input: s = "ab", goal = "ba"
Output: true

Example 2:

Input: s = "ab", goal = "ab"
Output: false

Example 3:

Input: s = "aa", goal = "aa"
Output: true

Example 4:

Input: s = "aaaaaaabc", goal = "aaaaaaacb"
Output: true

Clarifying Questions

1. What are the constraints on the lengths of s and goal?
   • Both s and goal have lengths between 1 and 2 * 10^4.
2. What character set do s and goal use?
   • Both strings consist of lowercase English letters only.
3. What should be the behavior if s and goal are of different lengths?
   • If the lengths are different, it should return false immediately.

Strategy

1. If the lengths of s and goal are different, return false.
2. If s is equal to goal, check if s contains any duplicate character. If there are duplicates, return true because swapping the duplicates will result in the same string.
3. If s is not equal to goal:
   • Identify the indices where s and goal differ.
   • If the number of differing positions is not exactly 2, return false because only one swap is allowed.
   • Check if swapping these differing characters in s will make it equal to goal.

Code

public class BuddyStrings {
    public boolean buddyStrings(String s, String goal) {
        // Step 1: Check length
        if (s.length() != goal.length()) {
            return false;
        }

        // Step 2: If strings are equal, check for duplicate characters
        if (s.equals(goal)) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
                if (count[c - 'a'] > 1) {  // If any character appears more than once
                    return true;
                }
            }
            return false;  // No duplicate characters found
        }

        // Step 3: Find indices where characters differ
        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 {
                    return false;  // More than 2 differences
                }
            }
        }

        // Step 4: Check if swapping makes the strings equal
        return (second != -1 && 
                s.charAt(first) == goal.charAt(second) && 
                s.charAt(second) == goal.charAt(first));
    }
}

Time Complexity

• The time complexity of this solution is O(N), where N is the length of the string s or goal. This is because we either iterate through the string once to compare characters or to count duplicate characters.
• The space complexity is O(1) because the auxiliary space used is constant (an array of size 26 to keep count of characters).

This solution should be efficient and handle the constraints specified in the problem statement effectively.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?