Buddy Strings - Practice Coding Problems

Buddy Strings - Problem

Given two strings s and goal, return true if you can swap exactly two letters in s so that 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".

Input & Output

Example 1 — Valid Swap

$ Input: s = "ab", goal = "ba"

› Output: true

💡 Note: We can swap s[0] and s[1] to get "ba". The character 'a' at position 0 becomes position 1, and 'b' at position 1 becomes position 0.

Example 2 — Invalid Different Characters

$ Input: s = "ab", goal = "ab"

› Output: false

💡 Note: The strings are already identical, but we need exactly one swap. Since there are no duplicate characters, no valid swap exists.

Example 3 — Valid with Duplicates

$ Input: s = "aa", goal = "aa"

› Output: true

💡 Note: The strings are identical and contain duplicate characters. We can swap the two 'a's (positions 0 and 1) to get the same string.

Constraints

1 ≤ s.length, goal.length ≤ 2 × 10⁴
s and goal consist of lowercase letters

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Two strings that may differ at some positions

Swap Validation

Check if exactly one swap can make them equal

Result

Return true if valid swap exists, false otherwise

Key Takeaway

🎯 Key Insight: Buddy strings work when there are exactly 2 different positions (swappable) or identical strings with duplicate characters

Asked in

G Google 12 f Facebook 8

The key insight is that buddy strings are possible in exactly two cases: (1) strings differ at exactly 2 positions and those characters can be swapped, or (2) strings are identical with at least one duplicate character. Best approach uses frequency counting with difference analysis. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(n)	Try swapping every possible pair of characters in s
Character Frequency Analysis	O(n)	O(1)	Compare character frequencies and find mismatched positions

Brute Force — Algorithm Steps

Step 1: Check if strings have same length (early return false if not)
Step 2: Try every pair of indices (i, j) where i < j
Step 3: For each pair, swap s[i] and s[j] and check if result equals goal

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Strings

Compare s and goal

Try Swaps

Test each possible swap pair

Check Match

See if any swap creates goal

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(char* s, char* goal) {
    int len_s = strlen(s);
    int len_goal = strlen(goal);
    
    if (len_s != len_goal) {
        return false;
    }
    
    // Try every possible swap
    for (int i = 0; i < len_s; i++) {
        for (int j = i + 1; j < len_s; j++) {
            // Create swapped string
            char* swapped = malloc((len_s + 1) * sizeof(char));
            strcpy(swapped, s);
            
            // Swap characters
            char temp = swapped[i];
            swapped[i] = swapped[j];
            swapped[j] = temp;
            
            if (strcmp(swapped, goal) == 0) {
                free(swapped);
                return true;
            }
            
            free(swapped);
        }
    }
    
    return false;
}

int main() {
    char s[1001], goal[1001];
    fgets(s, sizeof(s), stdin);
    fgets(goal, sizeof(goal), stdin);
    
    // Remove newlines
    s[strcspn(s, "\n")] = 0;
    goal[strcspn(goal, "\n")] = 0;
    
    bool result = solution(s, goal);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Nested loops O(n²) for pairs, plus O(n) string comparison for each pair

⚠ Quadratic Growth

Space Complexity

O(n)

Creating temporary strings for each swap attempt

⚡ Linearithmic Space

59.1K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler