9

String manipulation and Kth lexicographically largest character query

 2 years ago
source link: https://www.geeksforgeeks.org/string-manipulation-and-kth-lexicographically-largest-character-query//
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

String manipulation and Kth lexicographically largest character query

shivammiglani09

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:

// Java Implementation
import 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 Structure
class 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);
}
}
Output
[d]

Time Complexity: O(N+(Q*logN))
Auxiliary Space: O(N)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK