Given a string S containing only uppercase English letters. You have to process Q queries of the given form:
- 1 x: Print the maximum size of the segment [i, j] where
and substring S[i…j] contains only the letter S[x]. - 2 x: change S[x] = ‘#’ .
Note: For both types of queries, S[x] will not contain the character ‘#’.
Examples:
Input: S = ‘AABBBCCCC’, queries = [[1 0], [2 1], [1 0], [2 2], [1 3]]
Output: 2 1 2
Explanation: Initially S = ‘AABBBCCCC’
- query[0], longest continuous substring formed by S[0] is ‘AA’ of length 2.
- query[1], S=’A#BBBCCCC’
- query[2], longest continuous substring formed by S[0] is ‘A’ of length 1.
- query[3], S=’A##BBCCCC’
- query[4], longest continuous substring formed by S[3] is ‘BB’ of length 2.
Input: S = ‘XXYYY’, queries = [[1 3], [2 3], [1 2]]
Output: 3 1
Explanation: Initially S=’XXYYY’
- query[0], longest continuous substring formed by S[3] is ‘YYY’ of length 3.
- query[1], S = ‘XXY#Y’
- query[2], longest continuous substring formed by s[2] is ‘Y’ of length 1.
Approach: To solve the problem follow the below idea:
We can use Binary Search on the ordered ranges formed by the consecutive similar letters, also Set data structure can be used to update those ranges efficiently.
Follow the steps to solve the problem:
- Create an ordered set of pairs ‘st‘ to store the ranges of consecutive characters.
- For each query of type 1 x:
- Use Binary search to find the range [L, R] in which the current index x lies.
- Simply print the range difference i.e.R-L+1 as the answer to the type 1 query.
- For each query of type 2 x:
- Delete the old range [L, R] in which the current index x lies.
- Insert new ranges i.e. L to x-1 and x+1 to R, into our set ‘st‘.
Below is the implementation of the above algorithm:
C++
#include <bits/stdc++.h>using namespace std;void fn(string s, int n, vector<vector<int> > queries){ // Set of pair to store the ranges set<pair<int, int> > st; // Storing the initial ranges of consecutive characters. for (int i = 0; i < n; i++) { int l = i; while (i + 1 < n && s[i] == s[i + 1]) { i++; } int r = i; st.insert({ l, r }); } // Processint the queries for (auto e : queries) { int type = e[0]; int index = e[1]; // Solving query of type 1 if (type == 1) { // Binary search on the valid range using // upperbound auto it = --st.upper_bound({ index, 1 << 30 }); int left = (*it).first; int right = (*it).second; cout << right - left + 1 << endl; } // Solving the query of type 2 else { // Binary search on the valid range using // upperbound auto it = --st.upper_bound({ index, 1 << 30 }); int left = (*it).first; int right = (*it).second; // Erase the old range st.erase(it); // Inserting the new ranges. if (left != index) st.insert({ left, index - 1 }); if (right != index) st.insert({ index + 1, right }); } }}int main(){ string s = "AABBBCCCC"; int n = s.size(); vector<vector<int> > queries = { { 1, 0 }, { 2, 1 }, { 1, 0 }, { 2, 2 }, { 1, 3 } };fn(s, n, queries);} |
Java
// Java Program to Implement above approachimport java.util.*;public class Main { static void fn(String s, int n, List<List<Integer>> queries) { // Set of pair to store the ranges TreeSet<Pair<Integer, Integer>> st = new TreeSet<>(); // Storing the initial ranges of consecutive characters. for (int i = 0; i < n; i++) { int l = i; while (i + 1 < n && s.charAt(i) == s.charAt(i + 1)) { i++; } int r = i; st.add(new Pair<>(l, r)); } // Processing the queries for (List<Integer> e : queries) { int type = e.get(0); int index = e.get(1); // Solving query of type 1 if (type == 1) { // Binary search on the valid range using floor Pair<Integer, Integer> queryPair = new Pair<>(index, 1 << 30); Pair<Integer, Integer> it = st.floor(queryPair); int left = it.first; int right = it.second; System.out.println(right - left + 1); } // Solving the query of type 2 else { // Binary search on the valid range using floor Pair<Integer, Integer> queryPair = new Pair<>(index, 1 << 30); Pair<Integer, Integer> it = st.floor(queryPair); int left = it.first; int right = it.second; // Erase the old range st.remove(it); // Inserting the new ranges. if (left != index) st.add(new Pair<>(left, index - 1)); if (right != index) st.add(new Pair<>(index + 1, right)); } } } public static void main(String[] args) { String s = "AABBBCCCC"; int n = s.length(); List<List<Integer>> queries = new ArrayList<>(); queries.add(Arrays.asList(1, 0)); queries.add(Arrays.asList(2, 1)); queries.add(Arrays.asList(1, 0)); queries.add(Arrays.asList(2, 2)); queries.add(Arrays.asList(1, 3)); fn(s, n, queries); } static class Pair<K, V> implements Comparable<Pair<K, V>> { K first; V second; Pair(K first, V second) { this.first = first; this.second = second; } @Override public int compareTo(Pair<K, V> other) { int cmp = ((Comparable<K>) first).compareTo(other.first); return cmp != 0 ? cmp : ((Comparable<V>) second).compareTo(other.second); } }} |
Python3
def fn(s, queries): # List of pairs to store the ranges st = [] # Storing the initial ranges of consecutive characters. n = len(s) i = 0 while i < n: l = i while i + 1 < n and s[i] == s[i + 1]: i += 1 r = i st.append((l, r)) i += 1 # Processing the queries for e in queries: type = e[0] index = e[1] # Solving query of type 1 if type == 1: count = 0 for l, r in st: if l <= index <= r: count += (r - l + 1) print(count) # Solving the query of type 2 else: i = 0 while i < len(st): left, right = st[i] if left <= index <= right: break i += 1 if i < len(st): st.pop(i) if left != index: st.insert(i, (left, index - 1)) if right != index: st.insert(i + 1, (index + 1, right))if __name__ == "__main__": s = "AABBBCCCC" queries = [ (1, 0), (2, 1), (1, 0), (2, 2), (1, 3) ] fn(s, queries) |
C#
// C# Program to Implement above approachusing System;using System.Collections.Generic;class Program{ static void fn(string s, List<List<int>> queries) { // Set of pairs to store the ranges HashSet<Tuple<int, int>> st = new HashSet<Tuple<int, int>>(); // Storing the initial ranges of consecutive characters. for (int i = 0; i < s.Length; i++) { int l = i; while (i + 1 < s.Length && s[i] == s[i + 1]) { i++; } int r = i; st.Add(new Tuple<int, int>(l, r)); } // Processing the queries foreach (var e in queries) { int type = e[0]; int index = e[1]; // Solving query of type 1 if (type == 1) { // Find the first range with its right bound greater than or equal to the index Tuple<int, int> range = null; foreach (var pair in st) { if (pair.Item2 >= index) { range = pair; break; } } if (range != null) { int left = range.Item1; int right = range.Item2; Console.WriteLine(right - left + 1); } } // Solving the query of type 2 else { // Find the range that contains the index Tuple<int, int> range = null; foreach (var pair in st) { if (pair.Item1 <= index && index <= pair.Item2) { range = pair; break; } } if (range != null) { int left = range.Item1; int right = range.Item2; // Remove the old range st.Remove(range); // Insert the new ranges if (left != index) { st.Add(new Tuple<int, int>(left, index - 1)); } if (right != index) { st.Add(new Tuple<int, int>(index + 1, right)); } } } } } static void Main(string[] args) { string s = "AABBBCCCC"; List<List<int>> queries = new List<List<int>> { new List<int> { 1, 0 }, new List<int> { 2, 1 }, new List<int> { 1, 0 }, new List<int> { 2, 2 }, new List<int> { 1, 3 } }; fn(s, queries); }} |
Javascript
class Pair { constructor(first, second) { this.first = first; this.second = second; } compareTo(other) { const cmp = this.first - other.first; return cmp !== 0 ? cmp : this.second - other.second; }}function fn(s, n, queries) { // Set of pairs to store the ranges const st = new Set(); // Storing the initial ranges of consecutive characters for (let i = 0; i < n; i++) { let l = i; while (i + 1 < n && s.charAt(i) === s.charAt(i + 1)) { i++; } let r = i; st.add(new Pair(l, r)); } // Processing the queries for (const e of queries) { const type = e[0]; const index = e[1]; // Solving query of type 1 if (type === 1) { // Binary search on the valid range using floor let left = -1; let right = -1; for (const it of st) { if (it.first <= index && it.second >= index) { left = it.first; right = it.second; break; } } console.log(right - left + 1); } // Solving the query of type 2 else { // Binary search on the valid range using floor let left = -1; let right = -1; for (const it of st) { if (it.first <= index && it.second >= index) { left = it.first; right = it.second; st.delete(it); break; } } // Inserting the new ranges if (left !== index) { st.add(new Pair(left, index - 1)); } if (right !== index) { st.add(new Pair(index + 1, right)); } } }}const s = "AABBBCCCC";const n = s.length;const queries = [ [1, 0], [2, 1], [1, 0], [2, 2], [1, 3],];fn(s, n, queries); |
Output
2 1 2
Time Complexity: O(N.logN + Q.logN), where N is the string size and Q is the number of queries.
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
