Swap For Longest Repeated Character Substring

• 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.

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.

1import java.util.ArrayList;2import java.util.HashMap;3import java.util.List;4import java.util.Map;5 6class Solution {7    public int maxRepOpt1(String text) {8        Map<Character, Integer> counts = new HashMap<>();9        for (char c : text.toCharArray()) {10            counts.put(c, counts.getOrDefault(c, 0) + 1);11        }12 13        Map<Character, List<int[]>> groups = new HashMap<>();14        int n = text.length();15        if (n == 0) return 0;16 17        int i = 0;18        while (i < n) {19            char c = text.charAt(i);20            int j = i;21            while (j < n && text.charAt(j) == c) {22                j++;23            }24            groups.computeIfAbsent(c, k -> new ArrayList<>()).add(new int[]{i, j - i});25            i = j;26        }27 28        int maxLen = 0;29        for (char c : groups.keySet()) {30            List<int[]> charGroups = groups.get(c);31            int totalCount = counts.get(c);32 33            // Case 1: Extend a single group34            for (int[] group : charGroups) {35                int len = group[1];36                maxLen = Math.max(maxLen, Math.min(len + 1, totalCount));37            }38 39            // Case 2: Merge two groups separated by one character40            for (int k = 0; k < charGroups.size() - 1; k++) {41                int[] group1 = charGroups.get(k);42                int[] group2 = charGroups.get(k + 1);43                44                // Check if groups are separated by one character45                if (group1[0] + group1[1] + 1 == group2[0]) {46                    int combinedLen = group1[1] + group2[1];47                    maxLen = Math.max(maxLen, Math.min(combinedLen + 1, totalCount));48                }49            }50        }51        return maxLen;52    }53}

• 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.

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.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int maxRepOpt1(String text) {6        Map<Character, Integer> counts = new HashMap<>();7        for (char c : text.toCharArray()) {8            counts.put(c, counts.getOrDefault(c, 0) + 1);9        }10 11        int maxLen = 0;12        for (char ch = 'a'; ch <= 'z'; ch++) {13            if (!counts.containsKey(ch)) {14                continue;15            }16            17            int totalCount = counts.get(ch);18            int left = 0;19            int others = 0; // Count of characters other than 'ch' in the window20 21            for (int right = 0; right < text.length(); right++) {22                if (text.charAt(right) != ch) {23                    others++;24                }25 26                // Shrink window if there are more than 1 'other' characters27                while (others > 1) {28                    if (text.charAt(left) != ch) {29                        others--;30                    }31                    left++;32                }33 34                // The current window [left, right] has at most one 'other' char.35                // Its length is a candidate for the max length.36                // However, we are limited by the total number of 'ch' available.37                int windowLen = right - left + 1;38                int achievableLen = Math.min(windowLen, totalCount);39                maxLen = Math.max(maxLen, achievableLen);40            }41        }42        return maxLen;43    }44}