We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Buddy Strings

Number: 889

Difficulty: Easy

Paid? No

Companies: DoorDash, Google, Zoho, Amazon, Bloomberg, Microsoft

Problem Description

Given two strings s and goal, determine if you can swap exactly two letters in s so that the resulting string is equal to goal.

Key Insights

  • The strings must be of the same length; otherwise, the swap can never form goal.
  • If s is identical to goal, a valid swap is possible only if there is a duplicate character (allowing a swap that doesn't change the string).
  • When s and goal are different, there must be exactly two indices i and j such that s[i] != goal[i] and s[j] != goal[j]. Additionally, swapping these two characters must produce goal.
  • Early termination is possible if more than two mismatches are found.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, since we iterate through the strings once. Space Complexity: O(n) in the worst case for storing mismatches (or O(1) if the number of differences is bounded by 2).

Solution

We check the length of s and goal. If they differ, return false. If s equals goal, we need to verify that s contains at least one duplicate character which can be swapped without affecting the string. Otherwise, we collect all indices where s and goal differ. If there are exactly two differences, we then check if swapping these characters in s gives goal. This approach uses simple iteration and, optionally, a set to check for duplicates.

Code Solutions

# Function to determine if two strings are buddy strings
def buddy_strings(s: str, goal: str) -> bool:
    # If the lengths are different, a valid swap is impossible
    if len(s) != len(goal):
        return False

    # If s equals goal, check for duplicate characters
    if s == goal:
        # A duplicate exists if the set of characters is smaller than the string length
        return len(set(s)) < len(s)
    
    # List to store indices where s and goal differ
    diff = []
    # Iterate over both strings
    for i in range(len(s)):
        # Record indices where the characters differ
        if s[i] != goal[i]:
            diff.append(i)
        # If more than two differences, early exit
        if len(diff) > 2:
            return False

    # Must have exactly 2 mismatches for a valid swap
    if len(diff) != 2:
        return False
    
    # Check if swapping the two differing characters in s results in goal
    return s[diff[0]] == goal[diff[1]] and s[diff[1]] == goal[diff[0]]

# Example usage:
#print(buddy_strings("ab", "ba"))  # Expected output: True
← Back to All Questions