Problem 1247

Abstract / Summary

Find the least swaps needed to make two strings identical by swapping characters at the same positions.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1247.py

class Solution:
    def minimumSwap(self, s1: str, s2: str) -> int:
        # count "x", "y"
        x  = s1.count("x") + s2.count("x")
        y  = s1.count("y") + s2.count("y")
        if (x & 1) or (y & 1):
            return -1

        # as well as differences between s1 and s2
        xy = yx = 0
        for a, b in zip(s1, s2):
            if a < b:
                xy += 1
            if a > b:
                yx += 1

        result  = xy // 2
        result += yx // 2
        result += xy & 1
        result += yx & 1
        return result
21 lines | 575 bytes | submitted March 11, 2024 | GitHub   11% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 65% (60k+ submissions).

Typical patterns to solve this problem:
  • Greedy
  • Math
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The implementation solves the problem of finding the smallest number of swaps required to make two equal-length strings composed only of the characters x and y identical. It first checks whether a solution is possible, then classifies the mismatched positions into two categories, and finally derives the answer using arithmetic on those counts. The algorithm runs in linear time with respect to the length of the input strings and uses only a constant amount of additional memory.

Counting Characters

The first step aggregates the total number of x characters and the total number of y characters across both strings. This is done with the built-in count method, which scans each string once.

x = s1.count("x") + s2.count("x")
y = s1.count("y") + s2.count("y")

By summing the counts from both strings, the code obtains the global parity of each character type, which is essential for the feasibility test that follows.

Detecting Impossibility

A solution exists only when both the total number of x characters and the total number of y characters are even. The code uses a bitwise AND with 1 to test the least-significant bit, which is an efficient way to check oddness.

if (x & 1) or (y & 1):
    return -1

If either count is odd, the function returns -1 immediately, indicating that no sequence of swaps can resolve the mismatch. This early exit prevents unnecessary work on impossible cases such as strings where the combined count of a character is odd.

Counting Mismatched Pairs

The algorithm then iterates over the paired characters of the two strings using zip. For each position it distinguishes two kinds of mismatches:

  • xy - the character in s1 is x and the character in s2 is y.
  • yx - the character in s1 is y and the character in s2 is x.

The code increments the appropriate counter based on the lexical comparison of the two characters.

xy = yx = 0
for a, b in zip(s1, s2):
    if a < b:
        xy += 1
    if a > b:
        yx += 1

Because the only possible characters are x and y, the relational operators a < b and a > b reliably identify the two mismatch types without needing explicit equality checks.

Computing Minimum Swaps

Once the mismatch counts are known, the answer is derived by pairing mismatches of the same type and handling any leftover single mismatches. Two mismatches of the same type can be resolved with a single swap, which is captured by integer division by two. Any remaining single mismatch of each type requires two swaps: one to create a complementary mismatch and another to resolve it. The code uses bitwise AND with 1 to detect the presence of an odd remainder.

result = xy // 2
result += yx // 2
result += xy & 1
result += yx & 1
return result

The first two lines add the swaps needed for paired mismatches. The last two lines add one extra swap for each mismatch type that has an odd count, effectively accounting for the two-swap pattern required to fix a solitary xy together with a solitary yx.

Edge Cases Handled

When both input strings are already identical, the loop finds no mismatches, leaving xy and yx at zero. The arithmetic then yields a result of zero, correctly indicating that no swaps are needed.

If the strings are empty, the count operations return zero, the parity check passes, and the loop does not execute. The final computation again returns zero, handling the empty-string edge case gracefully.

When the total number of x or y characters is odd, the early return of -1 captures cases where an odd character cannot be paired, such as "x" versus "y" of length one.

When there is exactly one xy mismatch and one yx mismatch, the division yields zero for both, and each odd remainder contributes one to the result, producing a total of two swaps, which matches the optimal sequence of swaps for that configuration.

Performance Optimizations

The solution leverages the built-in count method, which is implemented in C and runs faster than a manual Python loop for counting characters. By aggregating the counts from both strings in a single expression, the code avoids extra temporary variables.

The parity test uses a bitwise operation (& 1) instead of a modulo operation, which is marginally faster because it operates directly on the binary representation.

During the mismatch scan, the code relies on the ordering of the characters x and y in Unicode, allowing the use of < and > to differentiate mismatch types without additional conditionals. This reduces branching and keeps the loop body minimal.

The final calculation employs integer division (//) and bitwise AND (& 1) to extract quotients and remainders in a compact form, avoiding separate modulo operations. All arithmetic is performed with plain integers, ensuring that the runtime stays linear and the memory footprint remains constant regardless of input size.

written by openai gpt

ELI5 - Simplified Explanation

Imagine there are two lines of toy blocks, where each block is either marked with an x or a y. The goal is to make the two lines look exactly the same by swapping blocks between them.

First, the code looks at all the blocks in both lines combined. Since every swap involves two blocks, there must be an even number of x blocks and an even number of y blocks for this to be possible. If there is an odd number, it is impossible to finish the task, so the code gives up.

Next, the code goes through the lines and looks at the places where the blocks do not match. Sometimes a line has an x where the other has a y, or the other way around. The code keeps track of how many of these mismatched pairs exist.

When there are two mismatched pairs that are the same, like two spots where the first line has an x and the second has a y, they can be fixed with just one swap. The code counts how many groups of two can be fixed this way.

Sometimes there are leftover mismatched pairs that cannot be fixed in pairs. The last part of the code handles these remaining pieces by accounting for the extra swaps needed to make everything perfectly balanced. It adds up all these little moves to figure out the total number of swaps required to make the two lines identical.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 7 | μ = 6.85 | σ = 1.73

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ JS Python Java Go TS
MemoryLimitExceeded C++ Python
Progiez C++ Python Java
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
everthis JS
fartem Ruby
fsq C++
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
suxrobGM C#
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, JavaScript, Python, TypeScript
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
everthis JavaScript
fartem Ruby
fsq C++
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
suxrobGM C#
28 links | 15 authors | 8 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

5 solutions   March 11, 2024

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality