Swap For Longest Repeated Character Substring

medium sliding window string hash table

Problem

You are given a string text. You can swap two of the characters in the string at most once. Return the length of the longest substring with repeated characters that you can obtain after the swap.

Inputtext = "aaabaaa"

Output6

Swap the single 'b' with an 'a' from elsewhere to merge the two runs of three a's into a run of six.

text (letters only)

def max_rep_opt1(text):
    count = {}
    for c in text:
        count[c] = count.get(c, 0) + 1
    # groups of (char, run_length)
    groups = []
    i = 0
    while i < len(text):
        j = i
        while j < len(text) and text[j] == text[i]:
            j += 1
        groups.append((text[i], j - i))
        i = j
    best = 0
    for k, (ch, length) in enumerate(groups):
        # extend this run with one swapped-in char if a spare exists
        cand = min(length + 1, count[ch])
        best = max(best, cand)
        # merge two same-char runs separated by exactly one char
        if k + 2 < len(groups) and groups[k + 1][1] == 1 and groups[k + 2][0] == ch:
            merged = length + groups[k + 2][1]
            best = max(best, min(merged + 1, count[ch]))
    return best

function maxRepOpt1(text) {
  const count = {};
  for (const c of text) count[c] = (count[c] || 0) + 1;
  const groups = [];
  let i = 0;
  while (i < text.length) {
    let j = i;
    while (j < text.length && text[j] === text[i]) j++;
    groups.push([text[i], j - i]);
    i = j;
  }
  let best = 0;
  for (let k = 0; k < groups.length; k++) {
    const [ch, length] = groups[k];
    best = Math.max(best, Math.min(length + 1, count[ch]));
    if (k + 2 < groups.length && groups[k + 1][1] === 1 && groups[k + 2][0] === ch) {
      const merged = length + groups[k + 2][1];
      best = Math.max(best, Math.min(merged + 1, count[ch]));
    }
  }
  return best;
}

class Solution {
    public int maxRepOpt1(String text) {
        int[] count = new int[26];
        for (char c : text.toCharArray()) count[c - 'a']++;
        List<int[]> groups = new ArrayList<>();
        int i = 0, n = text.length();
        while (i < n) {
            int j = i;
            while (j < n && text.charAt(j) == text.charAt(i)) j++;
            groups.add(new int[]{ text.charAt(i) - 'a', j - i });
            i = j;
        }
        int best = 0;
        for (int k = 0; k < groups.size(); k++) {
            int ch = groups.get(k)[0], len = groups.get(k)[1];
            best = Math.max(best, Math.min(len + 1, count[ch]));
            if (k + 2 < groups.size() && groups.get(k + 1)[1] == 1 && groups.get(k + 2)[0] == ch) {
                int merged = len + groups.get(k + 2)[1];
                best = Math.max(best, Math.min(merged + 1, count[ch]));
            }
        }
        return best;
    }
}

int maxRepOpt1(string text) {
    int count[26] = {0};
    for (char c : text) count[c - 'a']++;
    vector<pair<int,int>> groups;
    int i = 0, n = text.size();
    while (i < n) {
        int j = i;
        while (j < n && text[j] == text[i]) j++;
        groups.push_back({ text[i] - 'a', j - i });
        i = j;
    }
    int best = 0;
    for (int k = 0; k < (int)groups.size(); k++) {
        int ch = groups[k].first, len = groups[k].second;
        best = max(best, min(len + 1, count[ch]));
        if (k + 2 < (int)groups.size() && groups[k + 1].second == 1 && groups[k + 2].first == ch) {
            int merged = len + groups[k + 2].second;
            best = max(best, min(merged + 1, count[ch]));
        }
    }
    return best;
}

Explanation

We can do one swap to make the longest possible run of a single repeated letter. The neat idea is to first squash the string into groups — consecutive runs of the same character — and also count how many of each letter exist in total.

For each group (ch, length), one swap can extend that run by a single character, but only if there is a spare ch sitting elsewhere. That candidate is min(length + 1, count[ch]) — we cannot borrow a letter we do not have.

There is a second, better case: two runs of the same letter separated by exactly one other character. If group k + 1 has length 1 and group k + 2 is the same letter, swapping that single separator can merge both runs. The merged length is length + groups[k+2][1], plus one more if a spare ch exists, again capped by count[ch].

We try both cases for every group and keep the largest result in best.

Example: text = "aaabaaa". Two runs of three a's are split by a single b. Swapping that b with an a from elsewhere merges them into six a's, so the answer is 6.

Time: O(n) Space: O(n)