Swap For Longest Repeated Character Substring — Medium Problem & Solution

You may swap two characters of text at most once (any two positions, not necessarily adjacent).

Difficulty: Medium
Topics: Strings, Hash Table, Binary Search, Sliding Window
Asked at: Amazon, Google, Intuit
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You may swap two characters of text at most once (any two positions, not necessarily adjacent).

Return the length of the longest substring of a single repeated character you can obtain.

Example 1

Input: text = "ababa"
Output: 3
Explanation: Swapping the first b with the last a gives "aaaba".

Example 2

Input: text = "aaabaaa"
Output: 6
Explanation: Swapping the b with an a outside joins the two runs.

Example 3

Input: text = "aaaaa"
Output: 5
Explanation: Nothing to gain — the swap can be a no-op.

Constraints

1 <= text.length <= 20000
text consists of lowercase English letters.

How to solve Swap For Longest Repeated Character Substring

The answer always comes from one of two shapes: a single run extended by one borrowed character, or two same-character runs bridged across a single gap. Both are capped by how many of that character exist in total, since a swap moves a character rather than creating one.

Approach

Tally the total occurrences of each character.
Split the text into runs (char, length).
For each run, consider min(length + 1, total[char]).
When the next run is a single character and the one after repeats the same letter, also consider min(len1 + len2 + 1, total[char]).

Why it works

A swap brings in at most one extra copy of the target character, so no answer can exceed total[char], and the + 1 is only realisable when a spare copy exists outside the run — which the min enforces. Any optimal final run occupies contiguous positions, so it either sits inside one original run plus one borrowed slot, or spans exactly one foreign character between two runs; a gap of two or more cannot be closed by a single swap.

Complexity

Time — O(n)
Space — O(n)

Pitfalls

Forgetting the min with the total count over-counts when every copy of the character is already inside the run.
Bridging across a gap wider than one character is not achievable with one swap.
The bridge case must check the run after the gap has the same character.

Reference solution

Python

def maxRepOpt1(text: str) -> int:
    total = {}
    for ch in text:
        total[ch] = total.get(ch, 0) + 1
    runs = []
    i = 0
    n = len(text)
    while i < n:
        j = i
        while j < n and text[j] == text[i]:
            j += 1
        runs.append((text[i], j - i))
        i = j
    best = 0
    for r in range(len(runs)):
        c, length = runs[r]
        best = max(best, min(length + 1, total[c]))
        if r + 2 < len(runs) and runs[r + 1][1] == 1 and runs[r + 2][0] == c:
            best = max(best, min(length + runs[r + 2][1] + 1, total[c]))
    return best

JavaScript

var maxRepOpt1 = function(text) {
    var n = text.length;
    var total = {};
    for (var i = 0; i < n; i++) {
        var ch = text.charAt(i);
        total[ch] = (total[ch] || 0) + 1;
    }
    var runs = [];
    var p = 0;
    while (p < n) {
        var q = p;
        while (q < n && text.charAt(q) === text.charAt(p)) q++;
        runs.push([text.charAt(p), q - p]);
        p = q;
    }
    var best = 0;
    for (var r = 0; r < runs.length; r++) {
        var c = runs[r][0], len = runs[r][1];
        best = Math.max(best, Math.min(len + 1, total[c]));
        if (r + 2 < runs.length && runs[r + 1][1] === 1 && runs[r + 2][0] === c) {
            best = Math.max(best, Math.min(len + runs[r + 2][1] + 1, total[c]));
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue