Queries to find Kth greatest character in a range [L, R] from a string with updates

0 0 18 minutes read

Given a string str of length N, and Q queries of the following two types:

(1 L R K): Find the K^th greatest character (non-distinct) from the range of indices [L, R] (1-based indexing)
(2 J C): Replace the J^th character from the string by character C.

Examples:

Input: str = “abcddef”, Q = 3, queries[][] = {{1, 2, 5, 3}, {2, 4, g}, {1, 1, 4, 3}}
Output:
c
b
Explanation :
Query 1: String between indices (2, 5) is “bcdd”. The third largest character is ‘c’. Therefore, c is the required output.
Query 2: Replace S[4] by ‘g’. Therefore, S modifies to “abcgdef”.
Query 3: String between indices (1, 4) is “abcg”. The third largest character is ‘b’. Therefore, b is the required output.

Input: str=” afcdehgk”, Q = 4, queries[][] = {{1, 2, 5, 4}, {2, 5, m}, {1, 3, 7, 2}, {1, 1, 6, 4}}
Output:
c
h
d

Naive Approach: The simplest approach to solve the problem is as follows:

For each query of type ( 1 L R K ), find the substring of S from the range of indices [L, R], and sort this substring in non-increasing order. Print the character at the K^th index in the substring.
For each query of type ( 2 J C ), replace the J^th character in S by C.

C++

// C++ code for the approach
 
#include <bits/stdc++.h>
#include <algorithm>
#include <string>
using namespace std;
 
// Function to print the Kth greatest character
char printCharacter(string &str, int L, int R, int K) {
    // Extract the substring from [L, R]
    string substr = str.substr(L - 1, R - L + 1);
 
    // Sort the substring in non-increasing order
    sort(substr.begin(), substr.end(), greater<char>());
 
    // return the Kth character
    return substr[K - 1];
}
 
// Function to update the Jth character of the string
void updateString(string &str, int J, char C) {
    // Update the Jth character
    str[J - 1] = C;
}
 
// Driver Code
int main() {
    // Given string
    string str = "abcddef";
 
    // Count of queries
    int Q = 3;
 
    // Queries
    cout << printCharacter(str, 1, 2, 2)
         << endl;
    updateString(str, 4, 'g');
    cout << printCharacter(str, 1, 5, 4)
         << endl;
 
    return 0;
}

Java

// Java code for the approach
 
import java.util.*;
 
public class GFG {
    // Function to print the Kth greatest character
    public static char printCharacter(String str, int L,
                                      int R, int K)
    {
        // Extract the substring from [L, R]
        String substr = str.substring(L - 1, R);
 
        // Sort the substring in non-increasing order
        char[] charArr = substr.toCharArray();
        Arrays.sort(charArr);
        String sortedStr = new String(charArr);
        String revStr = new StringBuilder(sortedStr)
                            .reverse()
                            .toString();
 
        // return the Kth character
        return revStr.charAt(K - 1);
    }
 
    // Function to update the Jth character of the string
    public static void updateString(StringBuilder str,
                                    int J, char C)
    {
        // Update the Jth character
        str.setCharAt(J - 1, C);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given string
        String str = "abcddef";
 
        // Count of queries
        int Q = 3;
 
        // Queries
        System.out.println(printCharacter(str, 1, 2, 2));
        StringBuilder sb = new StringBuilder(str);
        updateString(sb, 4, 'g');
        str = sb.toString();
        System.out.println(printCharacter(str, 1, 5, 4));
    }
}

Python3

# Python3 code for the approach
 
# Function to print the Kth greatest character
def printCharacter(string, L, R, K):
  # Extract the substring from [L, R]
  substr = string[L-1:R]
  # Sort the substring in non-increasing order
  substr = sorted(substr, reverse=True)
 
  # Return the Kth character
  return substr[K-1]
 
# Function to update the Jth character of the string
def updateString(string, J, C):
  # Update the Jth character
  string = string[:J-1] + C + string[J:]
   
# Driver Code
if __name__ == '__main__':
  # Given string
  string = "abcddef"
  # Count of queries
  Q = 3
 
  # Queries
  print(printCharacter(string, 1, 2, 2))
  updateString(string, 4, 'g')
  print(printCharacter(string, 1, 5, 4))

C#

// C# code for the approach
 
using System;
 
class Program {
    // Function to print the Kth greatest character
    static char PrintCharacter(string str, int L, int R,
                               int K)
    {
        // Extract the substring from [L, R]
        string substr = str.Substring(L - 1, R - L + 1);
        // Convert the substring to a character array
        char[] chars = substr.ToCharArray();
        // Sort the character array in non-increasing order
        Array.Sort(chars);
        Array.Reverse(chars);
        // Return the Kth character
        return chars[K - 1];
    }
 
    // Function to update the Jth character of the string
    static string UpdateString(string str, int J, char C)
    {
        // Update the Jth character
        char[] chars = str.ToCharArray();
        chars[J - 1] = C;
 
        // Convert the character array back to a string and
        // return it
        return new string(chars);
    }
 
    static void Main(string[] args)
    {
        // Given string
        string str = "abcddef";
        // Count of queries
        int Q = 3;
 
        // Queries
        Console.WriteLine(PrintCharacter(str, 1, 2, 2));
        str = UpdateString(str, 4, 'g');
        Console.WriteLine(PrintCharacter(str, 1, 5, 4));
    }
}

Javascript

// JavaScript code for the approach
 
// Function to print the Kth greatest character
function printCharacter(str, L, R, K) {
    // Extract the substring from [L, R]
    let substr = str.substring(L - 1, R);
    // Sort the substring in non-increasing order
    substr = substr.split('').sort(function(a, b) {
        return b.localeCompare(a);
    }).join('');
 
    // return the Kth character
    return substr.charAt(K - 1);
}
 
// Function to update the Jth character of the string
function updateString(str, J, C) {
    // Update the Jth character
    str = str.substring(0, J - 1) + C + str.substring(J);
    return str;
}
 
// Driver Code
let str = "abcddef";
 
// Count of queries
let Q = 3;
 
// Queries
console.log(printCharacter(str, 1, 2, 2));
str = updateString(str, 4, 'g');
console.log(printCharacter(str, 1, 5, 4));
// This code is contributed by user_dtewbxkn77n

Output

a
b

Time Complexity: O ( Q * ( N log(N) ) ), where N logN is the computational complexity of sorting each substring.
Auxiliary Space: O(N)

The below code is the implementation of the above approach:

C++

// C++ Program to implement
// the above approach
 
#include "bits/stdc++.h"
using namespace std;
 
// Function to find the kth greatest
// character from the strijng
char find_kth_largest(string str, int k)
{
 
    // Sorting the string in
    // non-increasing Order
    sort(str.begin(), str.end(),
         greater<char>());
    return str[k - 1];
}
 
// Function to print the K-th character
// from the substring S[l] .. S[r]
char printCharacter(string str, int l,
                    int r, int k)
{
    // 0-based indexing
    l = l - 1;
    r = r - 1;
 
    // Substring of str from the
    // indices l to r.
    string temp
        = str.substr(l, r - l + 1);
 
    // Extract kth Largest character
    char ans
        = find_kth_largest(temp, k);
 
    return ans;
}
 
// Function to replace character at
// pos of str by the character s
void updateString(string str, int pos,
                  char s)
{
    // Index of S to be updated.
    int index = pos - 1;
    char c = s;
 
    // Character to be replaced
    // at index in S
    str[index] = c;
}
 
// Driver Code
int main()
{
    // Given string
    string str = "abcddef";
 
    // Count of queries
    int Q = 3;
 
    // Queries
    cout << printCharacter(str, 1, 2, 2)
         << endl;
    updateString(str, 4, 'g');
    cout << printCharacter(str, 1, 5, 4)
         << endl;
 
    return 0;
}

Java

// Java Program to implement
// the above approach
//include "bits/stdJava.h"
import java.util.*;
class GFG{
 
// Function to find the kth greatest
// character from the strijng
static char find_kth_largest(char []str, 
                             int k)
{
  // Sorting the String in
  // non-increasing Order
  Arrays.sort(str);
  reverse(str);
  return str[k - 1];
}
  static char[] reverse(char a[]) 
  {
    int i, n = a.length;
    char t;
    for (i = 0; i < n / 2; i++) 
    {
      t = a[i];
      a[i] = a[n - i - 1];
      a[n - i - 1] = t;
    }
    return a;
}
   
// Function to print the K-th character
// from the subString S[l] .. S[r]
static char printCharacter(String str, int l,
                           int r, int k)
{
  // 0-based indexing
  l = l - 1;
  r = r - 1;
 
  // SubString of str from the
  // indices l to r.
  String temp = str.substring(l, r - l + 1);
 
  // Extract kth Largest character
  char ans = 
    find_kth_largest(temp.toCharArray(), k);
 
  return ans;
}
 
// Function to replace character at
// pos of str by the character s
static void updateString(char []str, 
                         int pos, char s)
{
  // Index of S to be updated.
  int index = pos - 1;
  char c = s;
 
  // Character to be replaced
  // at index in S
  str[index] = c;
}
 
// Driver Code
public static void main(String[] args)
{
  // Given String
  String str = "abcddef";
 
  // Count of queries
  int Q = 3;
 
  // Queries
  System.out.print(printCharacter(str, 1, 
                                  2, 2) + "\n");
  updateString(str.toCharArray(), 4, 'g');
  System.out.print(printCharacter(str, 1, 
                                  5, 4) + "\n");
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python3 Program to implement
# the above approach
# Function to find the kth greatest
# character from the string
def find_kth_largest(strr, k):
 
    # Sorting the in
    # non-increasing Order
    strr = sorted(strr)
    strr = strr[:: -1]
    return strr[k - 1]
 
# Function to print the K-th character
# from the subS[l] .. S[r]
def printCharacter(strr, l, r, k):
   
    #0-based indexing
    l = l - 1
    r = r - 1
 
    # Subof strr from the
    # indices l to r.
    temp= strr[l: r - l + 1]
 
    #Extract kth Largest character
    ans = find_kth_largest(temp, k)
 
    return ans
 
# Function to replace character at
# pos of strr by the character s
def updateString(strr, pos, s):
    # Index of S to be updated.
    index = pos - 1
    c = s
 
    # Character to be replaced
    # at index in S
    strr[index] = c
 
# Driver Code
if __name__ == '__main__':
   
    # Given string
    strr = "abcddef"
    strr=[i for i in strr]
 
    # Count of queries
    Q = 3
 
    # Queries
    print(printCharacter(strr, 1, 2, 2))
    updateString(strr, 4, 'g')
    print(printCharacter(strr, 1, 5, 4))
 
# This code is contributed by Mohit Kumar 29

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to find the kth greatest
// character from the string
static char find_kth_largest(char []str, 
                             int k)
{
     
    // Sorting the String in
    // non-increasing Order
    Array.Sort(str);
    reverse(str);
     
    return str[k - 1];
}
 
static char[] reverse(char []a) 
{
    int i, n = a.Length;
    char t;
     
    for(i = 0; i < n / 2; i++) 
    {
        t = a[i];
        a[i] = a[n - i - 1];
        a[n - i - 1] = t;
    }
    return a;
}
 
// Function to print the K-th character
// from the subString S[l] .. S[r]
static char printchar(String str, int l,
                           int r, int k)
{
     
    // 0-based indexing
    l = l - 1;
    r = r - 1;
 
    // SubString of str from the
    // indices l to r.
    String temp = str.Substring(l, r - l + 1);
 
    // Extract kth Largest character
    char ans = find_kth_largest(
               temp.ToCharArray(), k);
 
    return ans;
}
 
// Function to replace character at
// pos of str by the character s
static void updateString(char []str, 
                         int pos, char s)
{
     
    // Index of S to be updated.
    int index = pos - 1;
    char c = s;
 
    // char to be replaced
    // at index in S
    str[index] = c;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given String
    String str = "abcddef";
 
    // Count of queries
    //int Q = 3;
 
    // Queries
    Console.Write(printchar(str, 1, 2, 2) + "\n");
    updateString(str.ToCharArray(), 4, 'g');
     
    Console.Write(printchar(str, 1, 5, 4) + "\n");
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
// Javascript Program to implement
// the above approach
//include "bits/stdJava.h"
 
// Function to find the kth greatest
// character from the strijng
function find_kth_largest(str,k)
{
  // Sorting the String in
  // non-increasing Order
  str.sort();
  reverse(str);
  return str[k - 1];
}
 
function reverse(a)
{
    let i, n = a.length;
    let t;
    for (i = 0; i < Math.floor(n / 2); i++)
    {
      t = a[i];
      a[i] = a[n - i - 1];
      a[n - i - 1] = t;
    }
    return a;
}
 
// Function to print the K-th character
// from the subString S[l] .. S[r]
function printCharacter(str,l,r,k)
{
  // 0-based indexing
  l = l - 1;
  r = r - 1;
  
  // SubString of str from the
  // indices l to r.
  let temp = str.substring(l, r - l + 1);
  
  // Extract kth Largest character
  let ans =
    find_kth_largest(temp.split(""), k);
  
  return ans;
}
 
// Function to replace character at
// pos of str by the character s
function updateString(str,pos,s)
{
  // Index of S to be updated.
  let index = pos - 1;
  let c = s;
  
  // Character to be replaced
  // at index in S
  str[index] = c;
}
 
// Driver Code
// Given String
let str = "abcddef";
// Count of queries
let Q = 3;
 
// Queries
document.write(printCharacter(str, 1,
                                2, 2) + "<br>");
updateString(str.split(""), 4, 'g');
document.write(printCharacter(str, 1,
                                5, 4) + "<br>");
 
 
 
// This code is contributed by avanitrachhadiya2155
</script>

Output:

a
b

Time Complexity: O(Q(r – l + 1) log (r – l + 1)) + O(Q), where Q is the number of queries, and r and l are the endpoints of the substring in each query.
Space Complexity: O(1)

Efficient Approach: The above approach can be optimized by precomputing the count of all the characters which are greater than or equal to character C ( ‘a’ ? C ? ‘z’ ) efficiently using a Fenwick Tree.
Follow the steps below to solve the problem:

Create a Fenwick Tree to store the frequencies of all characters from ‘a’ to ‘z‘
For every query of type 1, check for each character from ‘z’ to ‘a’, whether it is the K^th the greatest character.
In order to perform this, traverse from ‘z’ to ‘a’ and for each character, check if the count of all the characters traversed becomes ? K or not. Print the character for which the count becomes ? K.

Below is the implementation of the above approach:

C++

// C++ Program to implement
// the above approach
 
#include "bits/stdc++.h"
using namespace std;
 
// Maximum Size of a String
const int maxn = 100005;
 
// Fenwick Tree to store the
// frequencies of 26 alphabets
int BITree[26][maxn];
 
// Size of the String.
int N;
 
// Function to update Fenwick Tree for
// Character c at index val
void update_BITree(int index, char C,
                   int val)
{
    while (index <= N) {
 
        // Add val to current node
        // Fenwick Tree
        BITree[C - 'a'][index]
            += val;
 
        // Move index to parent node
        // in update View
        index += (index & -index);
    }
}
 
// Function to get sum of frequencies
// of character c till index
int sum_BITree(int index, char C)
{
 
    // Stores the sum
    int s = 0;
    while (index) {
 
        // Add current element of
        // Fenwick tree to sum
        s += BITree[C - 'a'][index];
 
        // Move index to parent node
        // in getSum View
        index -= (index & -index);
    }
    return s;
}
 
// Function to create the Fenwick tree
void buildTree(string str)
{
    for (int i = 1; i <= N; i++) {
 
        update_BITree(i, str[i], 1);
    }
    cout << endl;
}
 
// Function to print the kth largest
// character in the range of l to r
char printCharacter(string str, int l,
                    int r, int k)
{
 
    // Stores the count of
    // characters
    int count = 0;
 
    // Stores the required
    // character
    char ans;
 
    for (char C = 'z'; C >= 'a'; C--) {
 
        // Calculate frequency of
        // C in the given range
        int times = sum_BITree(r, C)
                    - sum_BITree(l - 1, C);
 
        // Increase count
        count += times;
 
        // If count exceeds K
        if (count >= k) {
 
            // Required character
            // found
            ans = C;
            break;
        }
    }
 
    return ans;
}
 
// Function to update character
// at pos by character s
void updateTree(string str, int pos,
                char s)
{
 
    // 0 based index system
    int index = pos;
    update_BITree(index, str[index], -1);
 
    str[index] = s;
    update_BITree(index, s, 1);
}
 
// Driver Code
int main()
{
    string str = "abcddef";
    N = str.size();
 
    // Makes the string 1-based indexed
    str = '#' + str;
 
    // Number of queries
    int Q = 3;
 
    // Construct the Fenwick Tree
    buildTree(str);
 
    cout << printCharacter(str, 1, 2, 2)
         << endl;
    updateTree(str, 4, 'g');
    cout << printCharacter(str, 1, 5, 4)
         << endl;
 
    return 0;
}

Java

// Java Program to implement
// the above approach
 
//include "bits/stdJava.h"
import java.util.*;
class GFG{
 
// Maximum Size of a String
static int maxn = 100005;
 
// Fenwick Tree to store the
// frequencies of 26 alphabets
static int [][]BITree = new int[26][maxn];
 
// Size of the String.
static int N;
 
// Function to update Fenwick Tree for
// Character c at index val
static void update_BITree(int index, 
                          char C, int val)
{
  while (index <= N) 
  {
    // Add val to current node
    // Fenwick Tree
    BITree[C - 'a'][index] += val;
 
    // Move index to parent node
    // in update View
    index += (index & -index);
  }
}
 
// Function to get sum of frequencies
// of character c till index
static int sum_BITree(int index, char C)
{
 
  // Stores the sum
  int s = 0;
  while (index > 0) 
  {
    // Add current element of
    // Fenwick tree to sum
    s += BITree[C - 'a'][index];
 
    // Move index to parent node
    // in getSum View
    index -= (index & -index);
  }
  return s;
}
 
// Function to create the Fenwick tree
static void buildTree(String str)
{
  for (int i = 1; i <= N; i++) 
  {
    update_BITree(i, str.charAt(i), 1);
  }
  System.out.println();
}
 
// Function to print the kth largest
// character in the range of l to r
static char printCharacter(String str, int l,
                           int r, int k)
{
  // Stores the count of
  // characters
  int count = 0;
 
  // Stores the required
  // character
  char ans = 0;
 
  for (char C = 'z'; C >= 'a'; C--) 
  {
    // Calculate frequency of
    // C in the given range
    int times = sum_BITree(r, C) - 
      sum_BITree(l - 1, C);
 
    // Increase count
    count += times;
 
    // If count exceeds K
    if (count >= k) 
    {
      // Required character
      // found
      ans = C;
      break;
    }
  }
  return ans;
}
 
// Function to update character
// at pos by character s
static void updateTree(String str, 
                       int pos, char s)
{
    // 0 based index system
    int index = pos;
    update_BITree(index, 
                  str.charAt(index), -1);
    str = str.substring(0, index) + s + 
          str.substring(index + 1);
    update_BITree(index, s, 1);
}
 
// Driver Code
public static void main(String[] args)
{
  String str = "abcddef";
  N = str.length();
 
  // Makes the String 1-based indexed
  str = '/' + str;
 
  // Number of queries
  int Q = 3;
 
  // Construct the Fenwick Tree
  buildTree(str);
 
  System.out.print(printCharacter(str, 1, 
                                  2, 2) + "\n");
  updateTree(str, 4, 'g');
  System.out.print(printCharacter(str, 1, 
                                  5, 4) + "\n");
 
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python3 Program to implement
# the above approach
 
# Maximum Size of a String
maxn = 100005
 
# Fenwick Tree to store the
# frequencies of 26 alphabets
BITree = [[0 for x in range(maxn)]
             for y in range(26)]
 
# Size of the String.
N = 0
 
# Function to update Fenwick Tree for
# Character c at index val
def update_BITree(index, C, val):
 
    while (index <= N):
 
        # Add val to current node
        # Fenwick Tree
        BITree[ord(C) -
               ord('a')][index]+= val
 
        # Move index to parent node
        # in update View
        index += (index & -index)
 
# Function to get sum of 
# frequencies of character 
# c till index
def sum_BITree(index, C):
 
    # Stores the sum
    s = 0
    while (index):
 
        # Add current element of
        # Fenwick tree to sum
        s += BITree[ord(C) -
                    ord('a')][index]
 
        # Move index to parent node
        # in getSum View
        index -= (index & -index)
    return s
 
# Function to create 
# the Fenwick tree
def buildTree(st):
   
    for i in range(1,
                   N + 1):
        update_BITree(i, 
                      st[i], 1)
     
    print()
 
# Function to print the 
# kth largest character 
# in the range of l to r
def printCharacter(st, l, 
                   r, k):
   
    # Stores the count of
    # characters
    count = 0
 
    for C in range(ord('z'), 
                   ord('a') -
                   1, -1):
 
        # Calculate frequency of
        # C in the given range
        times = (sum_BITree(r, chr(C)) -
                 sum_BITree(l - 1, chr(C)))
 
        # Increase count
        count += times
 
        # If count exceeds K
        if (count >= k):
 
            # Required character
            # found
            ans = chr( C)
            break
    
    return ans
 
# Function to update character
# at pos by character s
def updateTree(st, pos, s):
   
    # 0 based index system
    index = pos;
    update_BITree(index, 
                  st[index], -1)
 
    st.replace(st[index], s, 1)
    update_BITree(index, s, 1)
 
# Driver Code
if __name__ == "__main__":
   
    st = "abcddef"
    N = len(st)
 
    # Makes the string 
    # 1-based indexed
    st = '#' + st
 
    # Number of queries
    Q = 3
 
    # Construct the Fenwick Tree
    buildTree(st)
 
    print (printCharacter(st, 1, 
                          2, 2))
    updateTree(st, 4, 'g')
    print (printCharacter(st, 1, 
                          5, 4))
 
# This code is contributed by Chitranayal

C#

// C# Program to implement
// the above approach
using System;
class GFG{
 
// Maximum Size of a String
static int maxn = 100005;
 
// Fenwick Tree to store the
// frequencies of 26 alphabets
static int [,]BITree = new int[26, maxn];
 
// Size of the String.
static int N;
 
// Function to update Fenwick Tree for
// char c at index val
static void update_BITree(int index, 
                          char C, int val)
{
  while (index <= N) 
  {
    // Add val to current node
    // Fenwick Tree
    BITree[C - 'a', index] += val;
 
    // Move index to parent node
    // in update View
    index += (index & -index);
  }
}
 
// Function to get sum of frequencies
// of character c till index
static int sum_BITree(int index, char C)
{
  // Stores the sum
  int s = 0;
  while (index > 0) 
  {
    // Add current element of
    // Fenwick tree to sum
    s += BITree[C - 'a', index];
 
    // Move index to parent node
    // in getSum View
    index -= (index & -index);
  }
  return s;
}
 
// Function to create the Fenwick tree
static void buildTree(String str)
{
  for (int i = 1; i <= N; i++) 
  {
    update_BITree(i, str[i], 1);
  }
  Console.WriteLine();
}
 
// Function to print the kth largest
// character in the range of l to r
static char printchar(String str, int l,
                      int r, int k)
{
  // Stores the count of
  // characters
  int count = 0;
 
  // Stores the required
  // character
  char ans = (char)0;
 
  for (char C = 'z'; C >= 'a'; C--) 
  {
    // Calculate frequency of
    // C in the given range
    int times = sum_BITree(r, C) - 
                sum_BITree(l - 1, C);
 
    // Increase count
    count += times;
 
    // If count exceeds K
    if (count >= k) 
    {
      // Required character
      // found
      ans = C;
      break;
    }
  }
  return ans;
}
 
// Function to update character
// at pos by character s
static void updateTree(String str, 
                       int pos, char s)
{
  // 0 based index system
  int index = pos;
  update_BITree(index, 
                str[index], -1);
  str = str.Substring(0, index) + s + 
    str.Substring(index + 1);
  update_BITree(index, s, 1);
}
 
// Driver Code
public static void Main(String[] args)
{
  String str = "abcddef";
  N = str.Length;
 
  // Makes the String 1-based indexed
  str = '/' + str;
 
  // Number of queries
  int Q = 3;
 
  // Construct the Fenwick Tree
  buildTree(str);
 
  Console.Write(printchar(str, 1, 2, 2) + "\n");
  updateTree(str, 4, 'g');
  Console.Write(printchar(str, 1, 5, 4) + "\n");
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
// Javascript Program to implement
// the above approach
  
 
 
// Maximum Size of a String
let maxn = 100005;
 
// Fenwick Tree to store the
// frequencies of 26 alphabets
let BITree = new Array(26);
for(let i=0;i<26;i++)
{
    BITree[i]=new Array(maxn);
    for(let j=0;j<maxn;j++)
    {
        BITree[i][j]=0;
    }
     
}
 
// Size of the String.
let N;
 
// Function to update Fenwick Tree for
// Character c at index val
function update_BITree(index,C,val)
{
    while (index <= N)
  {
    // Add val to current node
    // Fenwick Tree
    BITree[C.charCodeAt(0) - 'a'.charCodeAt(0)][index] += val;
  
    // Move index to parent node
    // in update View
    index += (index & -index);
  }
}
 
// Function to get sum of frequencies
// of character c till index
function sum_BITree(index,C)
{
    // Stores the sum
  let s = 0;
  while (index > 0)
  {
    // Add current element of
    // Fenwick tree to sum
    s += BITree[C.charCodeAt(0) - 'a'.charCodeAt(0)][index];
  
    // Move index to parent node
    // in getSum View
    index -= (index & -index);
  }
  return s;
}
 
// Function to create the Fenwick tree
function buildTree(str)
{
    for (let i = 1; i <= N; i++)
  {
    update_BITree(i, str[i], 1);
  }
  document.write("<br>");
}
 
// Function to print the kth largest
// character in the range of l to r
function printCharacter(str,l,r,k)
{
    // Stores the count of
  // characters
  let count = 0;
  
  // Stores the required
  // character
  let ans = 0;
  
  for (let C = 'z'.charCodeAt(0); C >= 'a'.charCodeAt(0); C--)
  {
    // Calculate frequency of
    // C in the given range
    let times = sum_BITree(r, String.fromCharCode(C)) -
      sum_BITree(l - 1, String.fromCharCode(C));
  
    // Increase count
    count += times;
  
    // If count exceeds K
    if (count >= k)
    {
      // Required character
      // found
      ans = String.fromCharCode(C);
      break;
    }
  }
  return ans;
}
 
// Function to update character
// at pos by character s
function updateTree(str,pos,s)
{
    // 0 based index system
    let index = pos;
    update_BITree(index,
                  str[index], -1);
    str = str.substring(0, index) + s +
          str.substring(index + 1);
    update_BITree(index, s, 1);
}
 
// Driver Code
let str = "abcddef";
N = str.length;
 
// Makes the String 1-based indexed
str = '/' + str;
 
// Number of queries
let Q = 3;
 
// Construct the Fenwick Tree
buildTree(str);
 
document.write(printCharacter(str, 1,
                                2, 2) + "<br>");
updateTree(str, 4, 'g');
document.write(printCharacter(str, 1,
                                5, 4) + "<br>");
 
 
// This code is contributed by rag2127
</script>

Output:

a
b

Time Complexity: O( QlogN + NlogN )
Auxiliary Space: O(26 * maxn), where maxn denotes the maximum possible length of the string.

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 zambiatek!