algoadvance

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

Clarifying Questions

1. Length of Strings: Should s and goal always have the same length for a valid swap to be possible?
   • Yes, if the lengths of s and goal are not the same, a valid swap cannot make them equal.
2. Character Constraints: Are both strings guaranteed to consist of only lowercase alphabetic characters?
   • Yes, the problem assumes both strings contain lowercase alphabetic characters.
3. Edge Cases: Should we consider cases where the input strings are empty or of length 1?
   • Strings of length less than 2 cannot have any valid swaps as at least two characters are needed to swap.

Strategy

1. Length Check: First, check if the lengths of s and goal are different. If they are, we can immediately return false.

2. Identical Strings Handling: If the strings s and goal are identical, we need to check if there is at least one character that appears more than once in s. This will allow us to perform a valid swap without changing the string.

3. Different Strings: If the strings are not identical:

   • Compare characters of s and goal. Collect all the indices where the characters are different.
   • There must be exactly two indices where the characters differ, and swapping these two should make the strings equal.

Code

def buddy_strings(s: str, goal: str) -> bool:
    # Step 1: Length check
    if len(s) != len(goal):
        return False
    
    # Step 2: Check for identical strings
    if s == goal:
        seen = set()
        for char in s:
            if char in seen:
                return True
            seen.add(char)
        return False
    
    # Step 3: Compare differences
    pairs = []
    for i in range(len(s)):
        if s[i] != goal[i]:
            pairs.append((s[i], goal[i]))
        if len(pairs) > 2:
            return False
            
    return len(pairs) == 2 and pairs[0] == pairs[1][::-1]

# Example usage:
print(buddy_strings("ab", "ba"))  # Should return True
print(buddy_strings("ab", "ab"))  # Should return False
print(buddy_strings("aa", "aa"))  # Should return True
print(buddy_strings("aaaaaaabc", "aaaaaaacb"))  # Should return True
print(buddy_strings("", "aa"))  # Should return False

Time Complexity

• Length Check and Same Length Strings: This requires O(1) time since it’s a simple comparison.
• Identical Strings: Checking for duplicates would require O(n) time as we have to scan the entire string.
• Comparison of Differences: This will also be O(n) since we need to examine each character pair.

Thus, the overall time complexity of this solution is O(n), where n is the length of the input strings.

Try our interview co-pilot at AlgoAdvance.com

• 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?