Given a string s whose length is n and array queries of length q where each element of queries is either of type 1 query or type 2 query, the task is to perform each query in the same order as given in queries and return an array res such that the res array contains the answer for each type2 query in the same order as it appeared in queries that are explained below:
- Query type 1: [“1”, ind, char], “1” denotes this is a type 1 query. In this query, you have to change the character at index ind in s to character char. (Data type of ind, char is a string in input)
- Query type 2: [“2”, left, right, k], “2” denotes this is a type 2 query. In this query you have to return the kth lexicographically largest character in the substring of s (it is the kth largest character in sorted order, not the kth distinct character) starting from index left and ending at index right both left and right are inclusive. (Data type of left, right, k is a string in input)
Note: 0-based indexing is used.
Examples:
Input: n = 4, s = “abab”, q = 2, queries = {{“1”, “2”, “d”}, {“2”, “1”, “3”, “1”}}
Output: {“d”}
Explanation: The first query is of type 1 so after changing the character at index 2 to d s becomes abdb. Now the Second query is of type 2 in which the 1st(k = 1) lexicographically largest character is “d” in substring “bdb”(s[1:3]). So we returned an array with the result of type 2 query {“d”}.Input: n = 3, s = “aaa”, q = 3, queries = {{“1”, “1”, “e”}, {“1”, “2”, “c”}, {“2”, “1”, “2”, “2”}}
Output: {“c”}
Explanation: After applying the first two queries s becomes aec. Now for the last query which is a type 2 second largest character in substring s starting from index 1 to ending at index 2 is “c”.
Approach: This can be solved with the following idea:
The approach uses a segment tree to efficiently perform these queries. The segment tree is built using the given string of characters, where each node of the segment tree stores the frequency count of each character in the range represented by that node. For the update query, it updates the frequency count of the corresponding character in the segment tree, while for the kth smallest character query, it performs a binary search on the segment tree to find the kth smallest character in the given range. Finally, the code returns an ArrayList of the kth smallest character for each query of type 2.
Below are the steps involved in the implementation of the code:
- Update a character at a given index in the string.
- Find the kth largest character in a given range of the string.
- For query type 1, the code updates the segment tree by decrementing the count of the original character and incrementing the count of the new character.
- For query type 2, the code traverses the segment tree to get the count of each character in the given range and then iterates through the count array in reverse order to find the kth largest character.
- The code returns a list of the answers to all the queries.
Below is the code implementation of the above approach:
C++
#include <iostream>#include <vector>using namespace std;vector<vector<int>> seg;// Query Structurestruct Query { string type, a, b, c; Query(string t, string aa, string bb, string cc) : type(t), a(aa), b(bb), c(cc) {} Query(string t, string aa, string bb) : type(t), a(aa), b(bb), c("") {}};// Function to build treevoid buildTree(const vector<char>& a, int si, int ss, int se) { if (ss == se) { seg[si][a[ss] - 'a']++; return; } int mid = (ss + se) / 2; buildTree(a, 2 * si + 1, ss, mid); buildTree(a, 2 * si + 2, mid + 1, se); auto& a1 = seg[2 * si + 1]; auto& a2 = seg[2 * si + 2]; for (int i = 0; i < 26; i++) { seg[si][i] = a1[i] + a2[i]; }}// Update the particular stringvoid update(int si, int ss, int se, int pos, char val) { if (ss == se) { int in = 0; for (int i = 0; i < 26; i++) { if (seg[si][i] >= 1) { in = i; break; } } seg[si][in]--; seg[si][val - 'a']++; return; } int mid = (ss + se) / 2; if (pos <= mid) { update(2 * si + 1, ss, mid, pos, val); } else { update(2 * si + 2, mid + 1, se, pos, val); } auto& a1 = seg[2 * si + 1]; auto& a2 = seg[2 * si + 2]; for (int i = 0; i < 26; i++) { seg[si][i] = a1[i] + a2[i]; }}// Function to startvector<int> query(int si, int ss, int se, int qs, int qe) { if (qs > se || qe < ss) return vector<int>(26, 0); if (ss >= qs && se <= qe) return seg[si]; int mid = (ss + se) / 2; auto a1 = query(2 * si + 1, ss, mid, qs, qe); auto a2 = query(2 * si + 2, mid + 1, se, qs, qe); vector<int> ans(26, 0); for (int i = 0; i < 26; i++) { ans[i] = a1[i] + a2[i]; } return ans;}// Function to get the desired outputvector<char> easyTask(int n, const string& s, int q, const vector<Query>& queries) { seg.resize(4 * n, vector<int>(26, 0)); vector<char> ans; for (int i = 0; i < q; i++) { if (queries[i].type == "1") { int ind = stoi(queries[i].a); char val = queries[i].b[0]; update(0, 0, n - 1, ind, val); } else { int l = stoi(queries[i].a); int r = stoi(queries[i].b); int k = stoi(queries[i].c); auto arr = query(0, 0, n - 1, l, r); for (int j = 25; j >= 0; j--) { for (int kk = 0; kk < arr[j]; kk++) { k--; if (k == 0) { ans.push_back(static_cast<char>(j + 'a')); } } } } } return ans;}// Driver codeint main() { int n = 4; string s = "abab"; int q = 2; vector<Query> queries; queries.emplace_back("1", "2", "d"); queries.emplace_back("2", "1", "3", "1"); // Function call vector<char> result = easyTask(n, s, q, queries); // Print the result for (char c : result) { cout << c << " "; } return 0;} |
Java
// Java Implementationimport java.util.*;class Solution { static int seg[][]; // Function the get the desired output public static ArrayList<Character> easyTask(int n, String s, int q, query queries[]) { seg = new int[4 * n][26]; char c[] = s.toCharArray(); // Function to build tree buildTree(c, 0, 0, n - 1); ArrayList<Character> ans = new ArrayList<>(); for (int i = 0; i < q; i++) { if (queries[i].type.equals("1")) { int ind = Integer.parseInt(queries[i].a); char val = queries[i].b.charAt(0); update(0, 0, n - 1, ind, val); } else { int l = Integer.parseInt(queries[i].a); int r = Integer.parseInt(queries[i].b); int k = Integer.parseInt(queries[i].c); int arr[] = query(0, 0, n - 1, l, r); for (int j = 25; j >= 0; j--) { for (int kk = 0; kk < arr[j]; kk++) { k--; if (k == 0) { ans.add((char)(j + 'a')); } } } } } return ans; } // Function to build tree public static void buildTree(char a[], int si, int ss, int se) { if (ss == se) { seg[si][a[ss] - 'a']++; return; } int mid = (ss + se) / 2; buildTree(a, 2 * si + 1, ss, mid); buildTree(a, 2 * si + 2, mid + 1, se); int a1[] = seg[2 * si + 1]; int a2[] = seg[2 * si + 2]; for (int i = 0; i < 26; i++) { seg[si][i] = a1[i] + a2[i]; } } // Update the particular string public static void update(int si, int ss, int se, int pos, char val) { if (ss == se) { int in = 0; for (int i = 0; i < 26; i++) { if (seg[si][i] >= 1) { in = i; break; } } seg[si][in]--; seg[si][val - 'a']++; return; } int mid = (ss + se) / 2; if (pos <= mid) { update(2 * si + 1, ss, mid, pos, val); } else { update(2 * si + 2, mid + 1, se, pos, val); } int a1[] = seg[2 * si + 1]; int a2[] = seg[2 * si + 2]; for (int i = 0; i < 26; i++) { seg[si][i] = a1[i] + a2[i]; } } // Function to start public static int[] query(int si, int ss, int se, int qs, int qe) { if (qs > se || qe < ss) return new int[26]; if (ss >= qs && se <= qe) return seg[si]; int mid = (ss + se) / 2; int a1[] = query(2 * si + 1, ss, mid, qs, qe); int a2[] = query(2 * si + 2, mid + 1, se, qs, qe); // return max(p1, p2); int ans[] = new int[26]; for (int i = 0; i < 26; i++) { ans[i] = a1[i] + a2[i]; } return ans; } // Driver code public static void main(String[] args) { int n = 4; String s = "abab"; int q = 2; query[] queries = new query[2]; queries[0] = new query("1", "2", "d"); queries[1] = new query("2", "1", "3", "1"); // Function call ArrayList<Character> result = Solution.easyTask(n, s, q, queries); System.out.println(result); }}// Query Structureclass query { String type; String a; String b; String c; public query(String type, String a, String b, String c) { this.type = type; this.a = a; this.b = b; this.c = c; } public query(String type, String a, String b) { this(type, a, b, null); }} |
Python
class Solution: seg = [] # Static variable to store the segment tree # Function to get the desired output @staticmethod def easyTask(n, s, q, queries): # Initialize the segment tree Solution.seg = [[0] * 26 for _ in range(4 * n)] c = list(s) # Convert the string 's' to a list of characters # Function to build the segment tree Solution.buildTree(c, 0, 0, n - 1) ans = [] # List to store the answers to the queries for query in queries: if query['type'] == '1': # Type 1: Update the string ind = int(query['a']) # Get the index to update val = query['b'][0] # Get the new character value # Update the segment tree Solution.update(0, 0, n - 1, ind, val) else: # Type 2: Query for character at k-th position l = int(query['a']) # Get the left index of the query range r = int(query['b']) # Get the right index of the query range k = int(query['c']) # Get the k-th position # Perform the query on the segment tree arr = Solution.query(0, 0, n - 1, l, r) # Traverse the array from highest to lowest character position for j in range(25, -1, -1): for kk in range(arr[j]): k -= 1 if k == 0: # Found the k-th character, add to answer ans.append(chr(j + ord('a'))) return ans # Function to build the segment tree @staticmethod def buildTree(a, si, ss, se): if ss == se: # Increment the character count Solution.seg[si][ord(a[ss]) - ord('a')] += 1 return mid = (ss + se) // 2 Solution.buildTree(a, 2 * si + 1, ss, mid) # Build left child Solution.buildTree(a, 2 * si + 2, mid + 1, se) # Build right child for i in range(26): Solution.seg[si][i] = Solution.seg[2 * si + 1][i] + \ Solution.seg[2 * si + 2][i] # Update count # Update the particular string @staticmethod def update(si, ss, se, pos, val): if ss == se: in_ = 0 for i in range(26): if Solution.seg[si][i] >= 1: in_ = i break Solution.seg[si][in_] -= 1 # Decrement the old character count # Increment the new character count Solution.seg[si][ord(val) - ord('a')] += 1 return mid = (ss + se) // 2 if pos <= mid: Solution.update(2 * si + 1, ss, mid, pos, val) # Update left child else: Solution.update(2 * si + 2, mid + 1, se, pos, val) # Update right child for i in range(26): Solution.seg[si][i] = Solution.seg[2 * si + 1][i] + \ Solution.seg[2 * si + 2][i] # Update count # Function to perform the query @staticmethod def query(si, ss, se, qs, qe): if qs > se or qe < ss: return [0] * 26 # No overlap, return array of 26 zeros if ss >= qs and se <= qe: # Completely overlap, return the array from segment tree return Solution.seg[si] mid = (ss + se) // 2 a1 = Solution.query(2 * si + 1, ss, mid, qs, qe) # Query left child a2 = Solution.query(2 * si + 2, mid + 1, se, qs, qe) # Query right child ans = [0] * 26 for i in range(26): # Merge the results from left and right children ans[i] = a1[i] + a2[i] return ans # Driver code @staticmethod def main(): n = 4 # Length of the string s = "abab" # Input string q = 2 # Number of queries queries = [ # Update query at index 2 with character 'd' {'type': '1', 'a': '2', 'b': 'd'}, # Query for the first character in the range [1, 3] {'type': '2', 'a': '1', 'b': '3', 'c': '1'} ] # Function call result = Solution.easyTask(n, s, q, queries) print(result)# Query Structureclass Query: def __init__(self, type_, a, b, c=None): self.type = type_ self.a = a self.b = b self.c = c# Run the codeSolution.main() |
C#
using System;using System.Collections.Generic;public class Solution { // Static variable to store the segment tree private static int[, ] seg; // Function to get the desired output public static List<char> EasyTask(int n, string s, int q, List<Dictionary<string, string> > queries) { // Initialize the segment tree seg = new int[4 * n, 26]; char[] c = s.ToCharArray(); // Convert the string 's' to // a list of characters // Function to build the segment tree BuildTree(c, 0, 0, n - 1); List<char> ans = new List<char>(); // List to store the answers // to the queries foreach(var query in queries) { if (query["type"] == "1") // Type 1: Update the string { int ind = int.Parse( query["a"]); // Get the index to update char val = query["b"][0]; // Get the new // character value // Update the segment tree Update(0, 0, n - 1, ind, val); } else // Type 2: Query for the character at k-th // position { int l = int.Parse( query["a"]); // Get the left index of // the query range int r = int.Parse( query["b"]); // Get the right index of // the query range int k = int.Parse( query["c"]); // Get the k-th position // Perform the query on the segment tree int[] arr = Query(0, 0, n - 1, l, r); // Traverse the array from highest to lowest // character position for (int j = 25; j >= 0; j--) { for (int kk = 0; kk < arr[j]; kk++) { k--; if (k == 0) { // Found the k-th character, add // to the answer ans.Add((char)(j + 'a')); } } } } } return ans; } // Function to build the segment tree private static void BuildTree(char[] a, int si, int ss, int se) { if (ss == se) { // Increment the character count seg[si, a[ss] - 'a'] += 1; return; } int mid = (ss + se) / 2; // Build left child BuildTree(a, 2 * si + 1, ss, mid); // Build right child BuildTree(a, 2 * si + 2, mid + 1, se); for (int i = 0; i < 26; i++) { // Update count seg[si, i] = seg[2 * si + 1, i] + seg[2 * si + 2, i]; } } // Update the particular string private static void Update(int si, int ss, int se, int pos, char val) { if (ss == se) { int inIdx = 0; for (int i = 0; i < 26; i++) { if (seg[si, i] >= 1) { inIdx = i; break; } } // Decrement the old character count seg[si, inIdx]--; // Increment the new character count seg[si, val - 'a']++; return; } int mid = (ss + se) / 2; if (pos <= mid) { // Update left child Update(2 * si + 1, ss, mid, pos, val); } else { // Update right child Update(2 * si + 2, mid + 1, se, pos, val); } for (int i = 0; i < 26; i++) { // Update count seg[si, i] = seg[2 * si + 1, i] + seg[2 * si + 2, i]; } } // Function to perform the query private static int[] Query(int si, int ss, int se, int qs, int qe) { if (qs > se || qe < ss) { // No overlap, return an array of 26 zeros return new int[26]; } if (ss >= qs && se <= qe) { // Completely overlap, return the array from the // segment tree return GetRow(seg, si); } int mid = (ss + se) / 2; // Query left child int[] a1 = Query(2 * si + 1, ss, mid, qs, qe); // Query right child int[] a2 = Query(2 * si + 2, mid + 1, se, qs, qe); int[] ans = new int[26]; for (int i = 0; i < 26; i++) { // Merge the results from left and right // children ans[i] = a1[i] + a2[i]; } return ans; } // Helper function to get a row from a 2D array private static int[] GetRow(int[, ] array, int row) { int columns = array.GetLength(1); int[] rowArray = new int[columns]; for (int i = 0; i < columns; i++) { rowArray[i] = array[row, i]; } return rowArray; } // Driver code public static void Main() { int n = 4; // Length of the string string s = "abab"; // Input string int q = 2; // Number of queries List<Dictionary<string, string> > queries = new List<Dictionary<string, string> >{ // Update query at index 2 with character // 'd' new Dictionary<string, string>{ { "type", "1" }, { "a", "2" }, { "b", "d" } }, // Query for the first character in the // range [1, 3] new Dictionary<string, string>{ { "type", "2" }, { "a", "1" }, { "b", "3" }, { "c", "1" } } }; // Function call List<char> result = EasyTask(n, s, q, queries); Console.WriteLine(string.Join(" ", result)); }} |
Javascript
class Solution { static seg = []; // Function the get the desired output static easyTask(n, s, q, queries) { Solution.seg = Array.from({ length: 4 * n }, () => Array(26).fill(0)); const c = Array.from(s); // Function to build tree Solution.buildTree(c, 0, 0, n - 1); const ans = []; for (const query of queries) { if (query.type === '1') { const ind = parseInt(query.a); const val = query.b[0]; Solution.update(0, 0, n - 1, ind, val); } else { const l = parseInt(query.a); const r = parseInt(query.b); var k = parseInt(query.c); const arr = Solution.query(0, 0, n - 1, l, r); for (let j = 25; j >= 0; j--) { for (let kk = 0; kk < arr[j]; kk++) { k = k - 1; if (k === 0) { ans.push(String.fromCharCode(j + 'a'.charCodeAt(0))); } } } } } return ans; } // Function to build tree static buildTree(a, si, ss, se) { if (ss === se) { Solution.seg[si][a[ss].charCodeAt(0) - 'a'.charCodeAt(0)] += 1; return; } const mid = Math.floor((ss + se) / 2); Solution.buildTree(a, 2 * si + 1, ss, mid); Solution.buildTree(a, 2 * si + 2, mid + 1, se); for (let i = 0; i < 26; i++) { Solution.seg[si][i] = Solution.seg[2 * si + 1][i] + Solution.seg[2 * si + 2][i]; } } // Update the particular string static update(si, ss, se, pos, val) { if (ss === se) { let in_ = 0; for (let i = 0; i < 26; i++) { if (Solution.seg[si][i] >= 1) { in_ = i; break; } } Solution.seg[si][in_] -= 1; Solution.seg[si][val.charCodeAt(0) - 'a'.charCodeAt(0)] += 1; return; } const mid = Math.floor((ss + se) / 2); if (pos <= mid) { Solution.update(2 * si + 1, ss, mid, pos, val); } else { Solution.update(2 * si + 2, mid + 1, se, pos, val); } for (let i = 0; i < 26; i++) { Solution.seg[si][i] = Solution.seg[2 * si + 1][i] + Solution.seg[2 * si + 2][i]; } } // Function to start static query(si, ss, se, qs, qe) { if (qs > se || qe < ss) { return Array(26).fill(0); } if (ss >= qs && se <= qe) { return Solution.seg[si]; } let mid = Math.floor((ss + se) / 2); let a1 = Solution.query(2 * si + 1, ss, mid, qs, qe); let a2 = Solution.query(2 * si + 2, mid + 1, se, qs, qe); let ans = Array(26).fill(0); for (let i = 0; i < 26; i++) { ans[i] = a1[i] + a2[i]; } return ans; } // Driver code static main() { let n = 4; let s = "abab"; let q = 2; let queries = [ { 'type': '1', 'a': '2', 'b': 'd' }, { 'type': '2', 'a': '1', 'b': '3', 'c': '1' } ]; // Function call let result = Solution.easyTask(n, s, q, queries); console.log(result); }}// Query Structureclass Query { constructor(type_, a, b, c = null) { this.type = type_; this.a = a; this.b = b; this.c = c; }}Solution.main(); |
Output
[d]
Time Complexity: O(N+(Q*logN))
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!
Share your thoughts in the comments
