# Swap For Longest Repeated Character Substring
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/swap-for-longest-repeated-character-substring)
Canonical: https://scaleengineer.com/dsa/problems/swap-for-longest-repeated-character-substring
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Hash Table, String
**Companies:** [Nutanix](https://scaleengineer.com/companies/nutanix)
---
## Problem
You are given a string `text`. You can swap two of the characters in the `text`.

Return _the length of the longest substring with repeated characters_.

**Example 1:**

**Input:** text = "ababa"
**Output:** 3
**Explanation:** We can swap the first 'b' with the last 'a', or the last 'b' with the first 'a'. Then, the longest repeated character substring is "aaa" with length 3.

**Example 2:**

**Input:** text = "aaabaaa"
**Output:** 6
**Explanation:** Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring "aaaaaa" with length 6.

**Example 3:**

**Input:** text = "aaaaa"
**Output:** 5
**Explanation:** No need to swap, longest repeated character substring is "aaaaa" with length is 5.

**Constraints:**

* `1 <= text.length <= 2 * 104`
* `text` consist of lowercase English characters only.

# Approaches
## Grouping and Merging
This approach works by first identifying all consecutive groups of identical characters and their properties (like start index and length). It also pre-calculates the total frequency of each character. Then, for each character type (e.g., 'a', 'b', etc.), it considers two possibilities to form the longest substring:
1.  **Extending a single group:** Take an existing group of a character and use the single swap to replace an adjacent character with the same character, thus extending the group by one. This is only possible if there is another instance of that character available elsewhere in the string.
2.  **Merging two groups:** Find two groups of the same character that are separated by a single, different character. Use the swap to replace this separating character, effectively merging the two groups into one larger group.
**Time:** O(N), where N is the length of the string. The pre-computation of counts and groups takes O(N). The final loop iterates through each character's groups, and since the total number of groups across all characters is at most N, this step is also O(N). · **Space:** O(N), where N is the length of the string. In the worst-case scenario (e.g., "ababab..."), the number of groups can be O(N), leading to O(N) space for the `groups` map.
**Pros:** The logic is very direct and maps clearly to the problem's conditions (extending or merging).; It's relatively easy to reason about and debug.
**Cons:** Requires extra space to store the groups of characters, which can be proportional to the input string length in the worst-case scenario (e.g., a string like "ababab...").
### Explanation
The core idea is to break down the problem by character. For each character `c` from 'a' to 'z', we find the longest substring of `c`'s we can form.

First, we perform two pre-computation steps:
1.  We iterate through the string to count the total occurrences of each character. This gives us the `totalCount` for any character, which is the ultimate limit on the length of a substring of that character.
2.  We iterate through the string again to identify all contiguous blocks (groups) of identical characters. We store these groups, for example, in a `Map<Character, List<int[]>>`, where each `int[]` stores `[startIndex, length]`.

Once we have this information, we iterate through each character `c` present in the string and calculate the maximum length achievable for it:

- **Extending a single group:** For any group of `c`'s with length `L`, we can make it `L+1` long if we can swap in another `c`. This is possible if the total number of `c`'s in the string (`totalCount`) is greater than `L`. So, the potential length is `min(L + 1, totalCount)`.

- **Merging two groups:** If we find two groups of `c`'s with lengths `L1` and `L2` that are separated by just one other character (e.g., `...ccc_c...` where `_` is not `c`), we can swap that middle character. The merged length would be `L1 + L2`. If `totalCount` is greater than `L1 + L2`, it means there's at least one other `c` available to use for the swap, allowing us to also extend the group, making the length `L1 + L2 + 1`. This logic is neatly captured by `min(L1 + L2 + 1, totalCount)`.

The final answer is the maximum length found across all characters and all cases.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int maxRepOpt1(String text) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : text.toCharArray()) {
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }

        Map<Character, List<int[]>> groups = new HashMap<>();
        int n = text.length();
        if (n == 0) return 0;

        int i = 0;
        while (i < n) {
            char c = text.charAt(i);
            int j = i;
            while (j < n && text.charAt(j) == c) {
                j++;
            }
            groups.computeIfAbsent(c, k -> new ArrayList<>()).add(new int[]{i, j - i});
            i = j;
        }

        int maxLen = 0;
        for (char c : groups.keySet()) {
            List<int[]> charGroups = groups.get(c);
            int totalCount = counts.get(c);

            // Case 1: Extend a single group
            for (int[] group : charGroups) {
                int len = group[1];
                maxLen = Math.max(maxLen, Math.min(len + 1, totalCount));
            }

            // Case 2: Merge two groups separated by one character
            for (int k = 0; k < charGroups.size() - 1; k++) {
                int[] group1 = charGroups.get(k);
                int[] group2 = charGroups.get(k + 1);
                
                // Check if groups are separated by one character
                if (group1[0] + group1[1] + 1 == group2[0]) {
                    int combinedLen = group1[1] + group2[1];
                    maxLen = Math.max(maxLen, Math.min(combinedLen + 1, totalCount));
                }
            }
        }
        return maxLen;
    }
}
```
### Algorithm
- **Step 1: Pre-computation:**
  - Create a frequency map `counts` to store the total count of each character in the input `text`. This takes a single pass, O(N).
  - Create a map `groups` where the key is a character and the value is a list of its contiguous groups. Each group can be stored as an array or object containing its `start` index and `length`. This also takes a single pass, O(N).
- **Step 2: Calculate Maximum Length:**
  - Initialize a variable `maxLen` to 0.
  - Iterate through each character `c` that appeared in the text (i.e., each key in the `groups` map).
  - For each character `c`, retrieve its total count `totalCount` from the `counts` map and its list of groups `charGroups`.
  - **Case A (Extend a single group):** Iterate through each group in `charGroups`. For a group of length `L`, the maximum length we can achieve by extending it is `min(L + 1, totalCount)`. We update `maxLen` with the maximum value found.
  - **Case B (Merge two groups):** Iterate through adjacent pairs of groups in `charGroups`. If two groups with lengths `L1` and `L2` are separated by exactly one character, they can be merged. The potential length is `min(L1 + L2 + 1, totalCount)`. We update `maxLen` with this value if it's greater.
- **Step 3: Return Result:**
  - After checking all characters, `maxLen` will hold the length of the longest possible repeated character substring. Return `maxLen`.

## One-Pass Sliding Window
A more space-efficient solution uses the sliding window technique. The main idea is to iterate through each of the 26 lowercase characters and, for each one, find the longest substring we can form consisting of only that character, using at most one swap. We use a sliding window `[left, right]` to find the longest substring that contains at most one character different from the one we are currently considering. The length of this window represents a potential candidate for our answer. However, this length is capped by the total number of the target character available in the entire string. The overall maximum length found across all 26 characters is the result.
**Time:** O(N), where N is the length of the string. The outer loop runs a constant number of times (26), and for each run, the inner sliding window pointers (`left` and `right`) traverse the string at most once. Thus, the complexity is O(26 * N), which simplifies to O(N). · **Space:** O(1), as the `counts` map will store at most 26 key-value pairs, which is constant space. The sliding window itself uses a few pointer variables.
**Pros:** Highly efficient with optimal time complexity.; Uses constant extra space, making it superior to the grouping approach for large inputs with many groups.
**Cons:** The logic might be slightly less direct to grasp compared to the grouping approach, as it combines the cases of extending and merging into a single window condition.
### Explanation
This approach optimizes space by avoiding the storage of character groups. It still operates on the principle of checking each character ('a' through 'z') as a potential candidate for the longest repeating substring.

First, a single pass over the string is made to calculate the total frequency of each character. This is stored in a `counts` map or array. This frequency `counts[ch]` serves as an upper bound for the length of any substring composed of character `ch`.

Then, for each character `ch` from 'a' to 'z', we use a sliding window `[left, right]` to find the longest substring that can be turned into a solid block of `ch`'s with at most one swap. This means the window can contain at most one character that is not `ch`.

We expand the window by moving `right`. We keep a count of how many non-`ch` characters are in our current window. If this count exceeds 1, we must shrink the window from the left by advancing the `left` pointer until the window is valid again.

At every valid state of the window `[left, right]`, its length `right - left + 1` is a potential maximum. For example, a window `aaabaa` for character 'a' has length 6 and one 'other' character ('b'). We can swap this 'b' with an 'a' from elsewhere to get `aaaaaa`. The length we can achieve is therefore the window's length. But if the total number of 'a's in the whole string was, say, only 5, we could not form a string of 6 'a's. Thus, the achievable length for a given window is `min(window_length, total_count_of_ch)`.

We repeat this process for all 26 characters and take the maximum length found.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxRepOpt1(String text) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : text.toCharArray()) {
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }

        int maxLen = 0;
        for (char ch = 'a'; ch <= 'z'; ch++) {
            if (!counts.containsKey(ch)) {
                continue;
            }
            
            int totalCount = counts.get(ch);
            int left = 0;
            int others = 0; // Count of characters other than 'ch' in the window

            for (int right = 0; right < text.length(); right++) {
                if (text.charAt(right) != ch) {
                    others++;
                }

                // Shrink window if there are more than 1 'other' characters
                while (others > 1) {
                    if (text.charAt(left) != ch) {
                        others--;
                    }
                    left++;
                }

                // The current window [left, right] has at most one 'other' char.
                // Its length is a candidate for the max length.
                // However, we are limited by the total number of 'ch' available.
                int windowLen = right - left + 1;
                int achievableLen = Math.min(windowLen, totalCount);
                maxLen = Math.max(maxLen, achievableLen);
            }
        }
        return maxLen;
    }
}
```
### Algorithm
- **Step 1: Count Frequencies:**
  - First, iterate through the string once to compute the total frequency of each character. Store this in an array or hash map `counts`. This tells us the maximum possible length for any character's substring.
- **Step 2: Sliding Window for Each Character:**
  - Initialize `maxLen = 0`.
  - Loop through each character `ch` from 'a' to 'z'.
  - For each `ch`, apply a sliding window approach to the string `text`:
    - Initialize window pointers `left = 0`, and a counter `others = 0` for characters in the window that are not `ch`.
    - Iterate with a `right` pointer from `0` to `text.length() - 1` to expand the window.
    - If `text.charAt(right)` is not `ch`, increment `others`.
    - If `others` becomes greater than 1, the window is invalid (contains too many characters to fix with one swap). Shrink the window from the left by incrementing `left` until `others` is 1 or 0 again. While shrinking, if `text.charAt(left)` was not `ch`, decrement `others`.
    - After each expansion of `right`, the current window `[left, right]` is guaranteed to have at most one 'other' character. Calculate its length: `windowLen = right - left + 1`.
    - The actual length we can achieve is limited by the total count of `ch`. So, `achievableLen = min(windowLen, counts[ch])`.
    - Update the global maximum: `maxLen = max(maxLen, achievableLen)`.
- **Step 3: Return Result:**
  - After iterating through all 26 possible characters, `maxLen` will hold the answer.

# Solutions
### Java

```java
class Solution {
public
  int maxRepOpt1(String text) {
    int[] cnt = new int[26];
    int n = text.length();
    for (int i = 0; i < n; ++i) {
      ++cnt[text.charAt(i) - 'a'];
    }
    int ans = 0, i = 0;
    while (i < n) {
      int j = i;
      while (j < n && text.charAt(j) == text.charAt(i)) {
        ++j;
      }
      int l = j - i;
      int k = j + 1;
      while (k < n && text.charAt(k) == text.charAt(i)) {
        ++k;
      }
      int r = k - j - 1;
      ans = Math.max(ans, Math.min(l + r + 1, cnt[text.charAt(i) - 'a']));
      i = j;
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def maxRepOpt1(self, text: str) -> int: cnt = Counter(text) n = len(text) ans = i = 0 while i < n: j = i while j < n and text[j] == text[i]: j += 1 l = j - i k = j + 1 while k < n and text[k] == text[i]: k += 1 r = k - j - 1 ans = max(ans, min(l + r + 1, cnt[text[i]])) i = j return ans

```

### CPP

```cpp
class Solution {
public:
  int maxRepOpt1(string text) {
    int cnt[26] = {0};
    for (char &c : text) {
      ++cnt[c - 'a'];
    }
    int n = text.size();
    int ans = 0, i = 0;
    while (i < n) {
      int j = i;
      while (j < n && text[j] == text[i]) {
        ++j;
      }
      int l = j - i;
      int k = j + 1;
      while (k < n && text[k] == text[i]) {
        ++k;
      }
      int r = k - j - 1;
      ans = max(ans, min(l + r + 1, cnt[text[i] - 'a']));
      i = j;
    }
    return ans;
  }
};

```