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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Buddy Strings

Difficulty: Easy

Problem Description

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

Key Insights

  • The strings s and goal must have the same length to be considered for buddy strings.
  • If s equals goal, then there must be at least one character that appears more than once to allow a valid swap.
  • If s and goal differ at exactly two positions, swapping those two characters should make the strings equal.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we will:

  1. Check if the lengths of s and goal are equal. If not, return false.
  2. If s is equal to goal, check for duplicates in s. If a duplicate exists, return true; otherwise, return false.
  3. If s and goal are not equal, identify the indices where the characters differ. If there are exactly two differing indices, ensure that swapping the characters at these indices in s results in goal.

This approach utilizes a single traversal of the strings and constant space for the index storage.

Code Solutions

def buddyStrings(s: str, goal: str) -> bool:
    if len(s) != len(goal):
        return False

    if s == goal:
        return len(set(s)) < len(s)  # Check for duplicates

    # Find the indices where they differ
    diff = [(i, j) for i, (a, b) in enumerate(zip(s, goal)) if a != b]

    # There must be exactly two differences
    return len(diff) == 2 and s[diff[0][0]] == goal[diff[1][0]] and s[diff[1][0]] == goal[diff[0][0]]
← Back to All Questions