Longest Substring of One Repeating Character

• Convert the input string s to a mutable char array, sChars.
• Initialize an integer array result of size k to store the answers.
• Loop through each query from i = 0 to k-1:
  • Update the character in sChars at the given index: sChars[queryIndices[i]] = queryCharacters.charAt(i).
  • Initialize maxLength = 0, currentLength = 0.
  • Perform a linear scan through the sChars array.
  • During the scan, track the length of the current contiguous block of identical characters.
  • If sChars[j] is the same as sChars[j-1], increment currentLength. Otherwise, reset currentLength to 1.
  • Continuously update maxLength with the maximum currentLength seen so far.
  • After the scan, store the final maxLength in result[i].
• Return the result array.

The brute-force method is the most straightforward way to solve the problem. We begin by converting the string s into a more flexible data structure like a character array, which allows for O(1) time complexity for character updates.

For each of the k queries, we perform two main steps:

1. Update: We change the character at the specified queryIndices[i] to the new queryCharacters[i].
2. Recalculate: We iterate through the entire character array from beginning to end. We use a variable, say currentLength, to keep track of the length of the current substring of repeating characters. Another variable, maxLength, stores the maximum length found so far. As we iterate, if we encounter a character that is the same as the previous one, we increment currentLength. If the character changes, we reset currentLength to 1. At each step, we update maxLength to be the maximum of its current value and currentLength.

After scanning the whole array, maxLength will hold the answer for the current query. We store this value and proceed to the next query. This entire process is repeated for all k queries.

1class Solution {2    public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {3        int k = queryIndices.length;4        int[] ans = new int[k];5        char[] sChars = s.toCharArray();6 7        for (int i = 0; i < k; i++) {8            sChars[queryIndices[i]] = queryCharacters.charAt(i);9            10            int maxLength = 0;11            if (sChars.length > 0) {12                maxLength = 1;13                int currentLength = 1;14                for (int j = 1; j < sChars.length; j++) {15                    if (sChars[j] == sChars[j - 1]) {16                        currentLength++;17                    } else {18                        currentLength = 1;19                    }20                    maxLength = Math.max(maxLength, currentLength);21                }22            }23            ans[i] = maxLength;24        }25        return ans;26    }27}

• Initialize two TreeMaps: intervals to map a block's start index to its end index, and lengths to map a block's length to its frequency.
• Pre-process the initial string s in O(n) time to populate both TreeMaps with the initial blocks.
• For each query (idx, newChar):
  • If the character at idx is not changing, the answer remains the same.
  • Decomposition: Find the block [start, end] containing idx using intervals.floorEntry(idx). Remove this block from intervals and its length from lengths. Add back the two potential sub-blocks [start, idx-1] and [idx+1, end] if they are non-empty.
  • Update the character in the underlying character array: sArr[idx] = newChar.
  • Composition: A new block of length 1 is formed at idx. Check if this block can be merged with an adjacent block to the left (ending at idx-1) or to the right (starting at idx+1) if they consist of newChar. If a merge is possible, remove the old smaller blocks and add the new, larger merged block to the TreeMaps.
  • The answer for the query is the largest key in the lengths map, which can be retrieved with lengths.lastKey().
• Store the answer and repeat for all queries.

Instead of re-evaluating the entire string, we can focus only on the changes. An update at index idx can only affect the block of repeating characters that contains idx and potentially its immediate neighbors.

We use two TreeMap data structures to efficiently manage this:

1. intervals: A TreeMap<Integer, Integer> that maps the starting index of a block to its ending index. The sorted nature of TreeMap allows us to find which block an index idx belongs to in O(log N_blocks) time using floorEntry(idx).
2. lengths: A TreeMap<Integer, Integer> that serves as a multiset, mapping each block length to the count of blocks having that length. This lets us find the maximum length in O(log L_distinct) time by getting the last key (lastKey()).

Initialization: We first scan the string s once to identify all initial blocks and populate intervals and lengths.

Query Processing: For each query, we perform a two-phase update:

1. Decomposition: The character update at idx will break the block it currently belongs to. We find this block, remove it from our data structures, and add back the two smaller pieces it splits into (e.g., [start, idx-1] and [idx+1, end]).
2. Composition: After updating the character array, the new character at idx forms a new block of length 1. This block might be able to merge with its left and/or right neighbors if they now share the same character. We check for this, and if merges are possible, we remove the old, smaller blocks and add the new, larger merged block.

After these adjustments, the maximum length is simply the largest key present in our lengths map.

1import java.util.TreeMap;2import java.util.Map;3 4class Solution {5    char[] sArr;6    TreeMap<Integer, Integer> intervals; // {start -> end}7    TreeMap<Integer, Integer> lengths;   // {length -> count}8 9    public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {10        sArr = s.toCharArray();11        int n = s.length();12        intervals = new TreeMap<>();13        lengths = new TreeMap<>();14 15        // Initial build16        int start = 0;17        for (int i = 1; i <= n; i++) {18            if (i == n || sArr[i] != sArr[start]) {19                addInterval(start, i - 1);20                start = i;21            }22        }23 24        int k = queryIndices.length;25        int[] result = new int[k];26        for (int i = 0; i < k; i++) {27            int idx = queryIndices[i];28            char newChar = queryCharacters.charAt(i);29 30            if (sArr[idx] != newChar) {31                // --- Decomposition ---32                Map.Entry<Integer, Integer> entry = intervals.floorEntry(idx);33                int oldStart = entry.getKey();34                int oldEnd = entry.getValue();35                36                removeInterval(oldStart, oldEnd);37 38                if (idx > oldStart) {39                    addInterval(oldStart, idx - 1);40                }41                if (idx < oldEnd) {42                    addInterval(idx + 1, oldEnd);43                }44 45                // --- Composition ---46                sArr[idx] = newChar;47                int newStart = idx;48                int newEnd = idx;49 50                // Merge with left51                Map.Entry<Integer, Integer> leftEntry = intervals.floorEntry(idx - 1);52                if (leftEntry != null && leftEntry.getValue() == idx - 1 && sArr[idx - 1] == newChar) {53                    newStart = leftEntry.getKey();54                    removeInterval(newStart, idx - 1);55                }56 57                // Merge with right58                Integer rightEnd = intervals.get(idx + 1);59                if (rightEnd != null && sArr[idx + 1] == newChar) {60                    newEnd = rightEnd;61                    removeInterval(idx + 1, newEnd);62                }63                64                addInterval(newStart, newEnd);65            }66            67            result[i] = lengths.isEmpty() ? 0 : lengths.lastKey();68        }69        return result;70    }71 72    private void addInterval(int start, int end) {73        intervals.put(start, end);74        int len = end - start + 1;75        lengths.put(len, lengths.getOrDefault(len, 0) + 1);76    }77 78    private void removeInterval(int start, int end) {79        intervals.remove(start);80        int len = end - start + 1;81        lengths.put(len, lengths.get(len) - 1);82        if (lengths.get(len) == 0) {83            lengths.remove(len);84        }85    }86}

• Define a Node class to store segment information: maxLen, prefixLen, prefixChar, suffixLen, suffixChar, and total len.
• Implement a merge(leftNode, rightNode) function that combines two child nodes into a parent node, calculating the parent's attributes based on the children's.
• Implement a build(s, ...) function to recursively construct the segment tree from the bottom up. Leaf nodes correspond to single characters of s.
• Implement an update(idx, char, ...) function. When a query arrives, this function finds the corresponding leaf in the tree, updates its value, and then propagates the changes up to the root by calling the merge function on each parent along the path.
• For each query, call update() and then the answer is simply the maxLen value stored in the root of the tree (tree[0]).

This approach uses a segment tree, a classic data structure for this type of problem. Each node in the tree represents a range [L, R] of the string and stores crucial information about it.

For each node, we store:

• maxLen: The length of the longest repeating character substring fully contained within s[L...R].
• prefixLen, prefixChar: The length and character of the uniform prefix of s[L...R].
• suffixLen, suffixChar: The length and character of the uniform suffix of s[L...R].
• len: The total length of the range, R - L + 1.

Build: The tree is built recursively. A leaf node for index i will have maxLen=1, prefixLen=1, suffixLen=1, etc. Parent nodes are formed by a merge function that combines information from its left and right children.

Merge Logic: The key is the merge function. The maxLen of a parent is the maximum of left.maxLen, right.maxLen, and a potential new maximum formed by joining the suffix of the left child with the prefix of the right child, which is possible only if left.suffixChar == right.prefixChar. The prefix and suffix of the parent are also computed based on whether they can extend across the child boundary.

Update: An update to s[idx] corresponds to updating a single leaf in the segment tree. We traverse down to the leaf, change its value, and then traverse back up to the root, applying the merge logic at each level to update the ancestor nodes.

Query: After each update, the answer for the entire string is readily available as the maxLen value stored in the root node of the segment tree.

1class Solution {2    class Node {3        int maxLen;4        int prefixLen, suffixLen;5        char prefixChar, suffixChar;6        int len;7 8        Node(int maxLen, int prefixLen, char prefixChar, int suffixLen, char suffixChar, int len) {9            this.maxLen = maxLen;10            this.prefixLen = prefixLen;11            this.prefixChar = prefixChar;12            this.suffixLen = suffixLen;13            this.suffixChar = suffixChar;14            this.len = len;15        }16    }17 18    Node[] tree;19    char[] sArr;20 21    public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {22        int n = s.length();23        sArr = s.toCharArray();24        tree = new Node[4 * n];25        build(0, 0, n - 1);26 27        int k = queryIndices.length;28        int[] result = new int[k];29        for (int i = 0; i < k; i++) {30            int idx = queryIndices[i];31            char ch = queryCharacters.charAt(i);32            update(0, 0, n - 1, idx, ch);33            result[i] = tree[0].maxLen;34        }35        return result;36    }37 38    private Node merge(Node left, Node right) {39        if (left == null) return right;40        if (right == null) return left;41 42        int maxLen = Math.max(left.maxLen, right.maxLen);43        if (left.suffixChar == right.prefixChar) {44            maxLen = Math.max(maxLen, left.suffixLen + right.prefixLen);45        }46 47        int prefixLen = left.prefixLen;48        char prefixChar = left.prefixChar;49        if (left.prefixLen == left.len && left.prefixChar == right.prefixChar) {50            prefixLen += right.prefixLen;51        }52 53        int suffixLen = right.suffixLen;54        char suffixChar = right.suffixChar;55        if (right.suffixLen == right.len && right.suffixChar == left.suffixChar) {56            suffixLen += left.suffixLen;57        }58        59        return new Node(maxLen, prefixLen, prefixChar, suffixLen, suffixChar, left.len + right.len);60    }61 62    private void build(int node, int start, int end) {63        if (start == end) {64            tree[node] = new Node(1, 1, sArr[start], 1, sArr[start], 1);65            return;66        }67        int mid = start + (end - start) / 2;68        build(2 * node + 1, start, mid);69        build(2 * node + 2, mid + 1, end);70        tree[node] = merge(tree[2 * node + 1], tree[2 * node + 2]);71    }72 73    private void update(int node, int start, int end, int idx, char val) {74        if (start == end) {75            sArr[idx] = val;76            tree[node] = new Node(1, 1, val, 1, val, 1);77            return;78        }79        int mid = start + (end - start) / 2;80        if (start <= idx && idx <= mid) {81            update(2 * node + 1, start, mid, idx, val);82        } else {83            update(2 * node + 2, mid + 1, end, idx, val);84        }85        tree[node] = merge(tree[2 * node + 1], tree[2 * node + 2]);86    }87}