0559EasyHash TableString

One Mandatory Tile Exchange

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A departure board shows a row of lettered tiles, written as the string s. A technician has to carry out exactly one exchange: pick two different positions i and j of the row and put the tile from position i into position j and the tile from position j into position i. Skipping the exchange is not allowed, and the two positions chosen must be different, although the tiles sitting there may show the same letter.

Given s and the desired row goal, return true if some single exchange turns s into goal, and false otherwise. The two rows are not guaranteed to have the same number of tiles.

Examples

Example 1

Input: s = "abcd", goal = "abdc"
Output: true

Exchanging positions 2 and 3 of `s` moves c and d past each other and yields "abdc", which is the goal.

Example 2

Input: s = "abcd", goal = "abdb"
Output: false

The goal asks for a b at position 3, and `s` has no b outside position 1, so no exchange of two positions of `s` can produce it.

Example 3

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

Exchanging positions 1 and 2, which both carry b, leaves the row reading "abba", and that is the goal.

Constraints

1 <= s.length, goal.length <= 2 * 10^4
s and goal consist of lowercase English letters.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def buddy_strings(s: str, goal: str) -> bool:

Java

public boolean buddyStrings(String s, String goal)

The intended approach

Time O(n), a single pass over the row.Space O(1), a fixed table of 26 counters and at most two indices.

Rows of different widths are settled immediately. When the two rows are already the same string, the exchange still has to happen, so it has to be an exchange that changes nothing, which needs some letter present at two positions; a single pass of 26 counters answers that. Otherwise walk both rows collecting the positions where they disagree, bail out once a third one shows up, and accept only when there are two disagreements whose tiles hold each other's target letters.

Pythonentry point: buddy_strings

def buddy_strings(s, goal):
    # O(n) time, O(1) space (26 letter counters): rows of unequal width can never
    # match, an already matching row needs a letter it holds twice, and otherwise
    # the two rows must disagree in exactly two places that hold each other's
    # letters.
    if len(s) != len(goal):
        return False
    if s == goal:
        seen = [0] * 26
        for ch in s:
            k = ord(ch) - 97
            seen[k] += 1
            if seen[k] > 1:
                return True
        return False
    diff = []
    for i in range(len(s)):
        if s[i] != goal[i]:
            diff.append(i)
            if len(diff) > 2:
                return False
    if len(diff) != 2:
        return False
    a, b = diff
    return s[a] == goal[b] and s[b] == goal[a]

The obvious version

Enumerate every pair of distinct positions, apply that exchange to a copy of the row, and compare the copy with the goal. Unequal widths are rejected before the enumeration starts.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_buddy_strings(s, goal):
    if len(s) != len(goal):
        return False
    n = len(s)
    for i in range(n):
        for j in range(i + 1, n):
            chars = list(s)
            chars[i], chars[j] = chars[j], chars[i]
            if "".join(chars) == goal:
                return True
    return False

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in