Swap For Longest Repeated Character Substring

Medium
795.

Swap For Longest Repeated Character Substring

Swap For Longest Repeated Character Substring is a medium coding problem on strings, hash table and binary search, asked in Amazon, Google, Intuit and Nutanix interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} text
 * @return {number}
 */
var maxRepOpt1 = function(text) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Swap For Longest Repeated Character Substring — Solution

Swap For Longest Repeated Character Substring solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Swap For Longest Repeated Character Substring is a medium coding problem on strings, hash table and binary search, asked in Amazon, Google, Intuit and Nutanix interviews.

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.

Hints for Swap For Longest Repeated Character Substring

  1. Hint 1

    Break the string into maximal runs of equal characters.

  2. Hint 2

    One swap can extend a single run by one — but only if that character occurs somewhere outside it.

  3. Hint 3

    Two runs of the same character separated by exactly one other character can be joined, again capped by the total occurrences.

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

  1. Tally the total occurrences of each character.
  2. Split the text into runs (char, length).
  3. For each run, consider min(length + 1, total[char]).
  4. 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

Java

public static int maxRepOpt1(String text) {
    int n = text.length();
    int[] total = new int[26];
    for (int i = 0; i < n; i++) total[text.charAt(i) - 'a']++;
    List<int[]> runs = new ArrayList<>();
    int p = 0;
    while (p < n) {
        int q = p;
        while (q < n && text.charAt(q) == text.charAt(p)) q++;
        runs.add(new int[] { text.charAt(p) - 'a', q - p });
        p = q;
    }
    int best = 0;
    for (int r = 0; r < runs.size(); r++) {
        int c = runs.get(r)[0], len = runs.get(r)[1];
        best = Math.max(best, Math.min(len + 1, total[c]));
        if (r + 2 < runs.size() && runs.get(r + 1)[1] == 1 && runs.get(r + 2)[0] == c) {
            best = Math.max(best, Math.min(len + runs.get(r + 2)[1] + 1, total[c]));
        }
    }
    return best;
}

C++

int maxRepOpt1(string text) {
    int n = (int) text.size();
    vector<int> total(26, 0);
    for (int i = 0; i < n; i++) total[text[i] - 'a']++;
    vector<pair<int, int>> runs;
    int p = 0;
    while (p < n) {
        int q = p;
        while (q < n && text[q] == text[p]) q++;
        runs.push_back(make_pair(text[p] - 'a', q - p));
        p = q;
    }
    int best = 0;
    for (int r = 0; r < (int) runs.size(); r++) {
        int c = runs[r].first, len = runs[r].second;
        best = max(best, min(len + 1, total[c]));
        if (r + 2 < (int) runs.size() && runs[r + 1].second == 1 && runs[r + 2].first == c) {
            best = max(best, min(len + runs[r + 2].second + 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets