String Range Queries to count number of distinct characters with updates

0 0 9 minutes read

Given a string S of length N, and Q queries of the following type:

Type 1: 1 i X Update the i-th character of the string with the given character, X. Type 2: L R Count number of distinct characters in the given range [L, R].

Constraint:

1<=N<=500000

1<=Q<20000

|S|=N

String S contains only lowercase alphabets.

Examples:

Input: S = “abcdbbd” Q = 6 2 3 6 1 5 z 2 1 1 1 4 a 1 7 d 2 1 7 Output: 3 1 5 Explanation: For the Queries: 1. L = 3, R = 6 The different characters are:c, b, d. ans = 3. 2. String after query updated as S=”abcdzbd”. 3. L = 1, R = 1 Only one different character. and so on process all queries.

Input: S = “aaaaa”, Q = 2 1 2 b 2 1 4 Output: 2

Naive approach:

Query type 1: Replace i-th character of the string with the given character. Query type 2: Traverse the string from L to R and count the number of distinct characters.

Below is the implementation of the above approach:

C++14

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number
// of distinct characters in
// the range [L, R]
void Query2(string S, int L, int R)
{
    int cnt = 0;
    for (int i = L - 1; i < R; i++) {
        bool found = false;
        for (int j = L - 1; j < i; j++) {
            if (S[i] == S[j]) {
                found = true;
                break;
            }
        }
        if (!found)
            cnt++;
    }
    cout << cnt << endl;
}
 
// Function to update the i-th
// character of the string
// with the given character X
void Query1(string& S, int i, char X) { S[i - 1] = X; }
 
// Driver code
int main()
{
    string S = "abcdbbd";
    int N = S.size();
 
    // Queries for sample input
    Query2(S, 3, 6);
    Query1(S, 5, 'z');
    Query2(S, 1, 1);
    Query1(S, 4, 'a');
    Query1(S, 7, 'd');
    Query2(S, 1, 7);
 
    return 0;
}

Java

import java.util.HashSet;
 
class Main {
   
      // Function to count the number
    // of distinct characters in
    // the range [L, R]
    static void Query2(String S, int L, int R) {
        int cnt = 0;
        for (int i = L - 1; i < R; i++) {
            boolean found = false;
            for (int j = L - 1; j < i; j++) {
                if (S.charAt(i) == S.charAt(j)) {
                    found = true;
                    break;
                }
            }
            if (!found)
                cnt++;
        }
        System.out.println(cnt);
    }
 
      // Function to update the i-th
    // character of the string
    // with the given character X
    static void Query1(StringBuilder S, int i, char X) {
        S.setCharAt(i - 1, X);
    }
 
   
      // Driver code
    public static void main(String[] args) {
        StringBuilder S = new StringBuilder("abcdbbd");
        int N = S.length();
 
        Query2(S.toString(), 3, 6);
        Query1(S, 5, 'z');
        Query2(S.toString(), 1, 1);
        Query1(S, 4, 'a');
        Query1(S, 7, 'd');
        Query2(S.toString(), 1, 7);
    }
}

Python3

# Function to count the number
# of distinct characters in
# the range [L, R]
def Query2(S, L, R):
    cnt = 0
    for i in range(L - 1, R):
        found = False
        for j in range(L - 1, i):
            if S[i] == S[j]:
                found = True
                break
        if not found:
            cnt += 1
    print(cnt)
 
# Function to update the i-th
# character of the string
# with the given character X
def Query1(S, i, X):
    S[i - 1] = X
 
# Driver code
if __name__ == "__main__":
    S = list("abcdbbd")
    N = len(S)
 
    # Queries for sample input
    Query2(S, 3, 6)
    Query1(S, 5, 'z')
    Query2(S, 1, 1)
    Query1(S, 4, 'a')
    Query1(S, 7, 'd')
    Query2(S, 1, 7)

Output

3
1
5

Time complexity: O(N²)
Space complexity: O(1)

Efficient approach: This approach is based on the Frequency-counting algorithm. The idea is to use a HashMap to map distinct characters of the string with an Ordered_set which stores indices of its all occurrence. Ordered_set is used because it is based on Red-Black tree, so insertion and deletion of character will taken O ( log N ).

Insert all characters of the string with its index into Hash-map
For query of type 1, erase the occurrence of character at index i and insert occurrence of character X at index i in Hash-map
For query of type 2, traverse all 26 characters and check if its occurrence is within the range [L, R], if yes then increment the count. After traversing print the value of count.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
#define ordered_set                 \
    tree<int, null_type, less<int>, \
         rb_tree_tag,               \
         tree_order_statistics_node_update>
 
// Function that returns the lower-
// bound of the element in ordered_set
int lower_bound(ordered_set set1, int x)
{
    // Finding the position of
    // the element
    int pos = set1.order_of_key(x);
 
    // If the element is not
    // present in the set
    if (pos == set1.size()) {
        return -1;
    }
 
    // Finding the element at
    // the position
    else {
        int element = *(set1.find_by_order(pos));
 
        return element;
    }
}
 
// Utility function to add the
// position of all characters
// of string into ordered set
void insert(
    unordered_map<int, ordered_set>& hMap,
    string S, int N)
{
    for (int i = 0; i < N; i++) {
        hMap[S[i] - 'a'].insert(i);
    }
}
 
// Utility function for update
// the character at position P
void Query1(
    string& S,
    unordered_map<int, ordered_set>& hMap,
    int pos, char c)
{
 
    // we delete the position of the
    // previous character as new
    // character is to be replaced
    // at the same position.
    pos--;
    int previous = S[pos] - 'a';
    int current = c - 'a';
    S[pos] = c;
    hMap[previous].erase(pos);
    hMap[current].insert(pos);
}
 
// Utility function to determine
// number of different characters
// in given range.
void Query2(
    unordered_map<int, ordered_set>& hMap,
    int L, int R)
{
    // Iterate over all 26 alphabets
    // and check if it is in given
    // range using lower bound.
    int count = 0;
    L--;
    R--;
    for (int i = 0; i < 26; i++) {
        int temp = lower_bound(hMap[i], L);
        if (temp <= R and temp != -1)
            count++;
    }
    cout << count << endl;
}
 
// Driver code
int main()
{
    string S = "abcdbbd";
    int N = S.size();
 
    unordered_map<int, ordered_set> hMap;
 
    // Insert all characters with its
    // occurrence in the hash map
    insert(hMap, S, N);
 
    // Queries for sample input
    Query2(hMap, 3, 6);
    Query1(S, hMap, 5, 'z');
    Query2(hMap, 1, 1);
    Query1(S, hMap, 4, 'a');
    Query1(S, hMap, 7, 'd');
    Query2(hMap, 1, 7);
 
    return 0;
}

Java

import java.util.*;
import java.util.stream.*;
 
public class Main {
    public static void main(String[] args) {
        String S = "abcdbbd";
        int N = S.length();
        Map<Integer, TreeSet<Integer>> hMap = new HashMap<>();
        // Insert all characters with its
        // occurrence in the hash map
        insert(hMap, S, N);
        //Queries for sample input
        query2(hMap, 3, 6);
        query1(S, hMap, 5, 'z');
        query2(hMap, 1, 1);
        query1(S, hMap, 4, 'a');
        query1(S, hMap, 7, 'd');
        query2(hMap, 1, 7);
    }
 
    // Utility function to add the
    // position of all characters
    // of string into TreeSet
    public static void insert(Map<Integer, TreeSet<Integer>> hMap, String S, int N) {
        for (int i = 0; i < N; i++) {
            int c = S.charAt(i) - 'a';
            if (!hMap.containsKey(c)) {
                hMap.put(c, new TreeSet<>());
            }
            hMap.get(c).add(i);
        }
    }
 
    // Utility function for update
    // the character at position P
    public static void query1(String S, Map<Integer, TreeSet<Integer>> hMap, int pos, char c) {
        // We delete the position of the
        // previous character as new
        // character is to be replaced
        // at the same position.
        pos--;
        int previous = S.charAt(pos) - 'a';
        int current = c - 'a';
        char[] chars = S.toCharArray();
        chars[pos] = c;
        S = String.valueOf(chars);
        hMap.get(previous).remove(pos);
        if (!hMap.containsKey(current)) {
            hMap.put(current, new TreeSet<>());
        }
        hMap.get(current).add(pos);
    }
 
    // Utility function to determine
    // number of different characters
    // in given range.
    public static void query2(Map<Integer, TreeSet<Integer>> hMap, int L, int R) {
        // Iterate over all 26 alphabets
        // and check if it is in given
        // range using floor() method.
        int count = 0;
        L--;
        R--;
        for (int i = 0; i < 26; i++) {
            if (hMap.containsKey(i)) {
                Integer temp = hMap.get(i).floor(R);
                if (temp != null && temp >= L) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

Python3

# Python equivalent of the above java code
import collections
 
# Insert all characters with its
# occurrence in the hash map
def insert(hMap, S, N): 
    for i in range(N): 
        c = ord(S[i]) - ord('a') 
        if c not in hMap: 
            hMap = [] 
        hMap.append(i) 
 
# Utility function for update
# the character at position P
def query1(S, hMap, pos, c): 
    # We delete the position of the
    # previous character as new
    # character is to be replaced
    # at the same position.
    pos -= 1
    previous = ord(S[pos]) - ord('a') 
    current = ord(c) - ord('a') 
    S = S[:pos] + c + S[pos+1:] 
    hMap[previous].remove(pos) 
    if current not in hMap: 
        hMap[current] = [] 
    hMap[current].append(pos) 
 
# Utility function to determine
# number of different characters
# in given range.
def query2(hMap, L, R): 
   
    # Iterate over all 26 alphabets
    # and check if it is in given
    # range using floor() method.
    count = 0
    L -= 1
    R -= 1
    for i in range(26): 
        if i in hMap.keys(): 
            temp = list(filter(lambda x: x<=R and x>=L, hMap[i])) 
            if len(temp): 
                count += 1
    print(count) 
 
if __name__ == "__main__":
    S = "abcdbbd"
    N = len(S)
    hMap = collections.defaultdict(list)
    insert(hMap, S, N)
     
    # Queries for sample input
    query2(hMap, 3, 6)
    query1(S, hMap, 5, 'z')
    query2(hMap, 1, 1)
    query1(S, hMap, 4, 'a')
    query1(S, hMap, 7, 'd')
    query2(hMap, 1, 7)

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
 
public class GFG {
    public static void Main() {
    string S = "abcdbbd";
    int N = S.Length;
    Dictionary<int, List<int>> hMap = new Dictionary<int, List<int>>();
    Insert(hMap, S, N);
 
        // Queries for sample input
        Query2(hMap, 3, 6);
        Query1(S, hMap, 5, 'z');
        Query2(hMap, 1, 1);
        Query1(S, hMap, 4, 'a');
        Query1(S, hMap, 7, 'd');
        Query2(hMap, 1, 7);
    }
 
    // Insert all characters with its occurrence in the hash map
    public static void Insert(Dictionary<int, List<int>> hMap, string S, int N) {
        for (int i = 0; i < N; i++) {
            int c = S[i] - 'a';
            if (!hMap.ContainsKey(c)) {
                hMap = new List<int>();
            }
            hMap.Add(i);
        }
    }
 
    // Utility function for update the character at position P
    public static void Query1(string S, Dictionary<int, List<int>> hMap, int pos, char c) {
        // We delete the position of the previous character as new
        // character is to be replaced at the same position.
        pos -= 1;
        int previous = S[pos] - 'a';
        int current = c - 'a';
        S = S.Substring(0, pos) + c + S.Substring(pos + 1);
        hMap[previous].Remove(pos);
        if (!hMap.ContainsKey(current)) {
            hMap[current] = new List<int>();
        }
        hMap[current].Add(pos);
    }
 
    // Utility function to determine number of different characters in given range.
    public static void Query2(Dictionary<int, List<int>> hMap, int L, int R) {
        // Iterate over all 26 alphabets
        // and check if it is in given range using floor() method.
        int count = 0;
        L -= 1;
        R -= 1;
        for (int i = 0; i < 26; i++) {
            if (hMap.ContainsKey(i)) {
                var temp = hMap[i].Where(x => x <= R && x >= L).ToList();
                if (temp.Count > 0) {
                    count += 1;
                }
            }
        }
        Console.WriteLine(count);
    }
}
// This code is contributed by codebraxnzt

Javascript

function main() {
  const S = 'abcdbbd';
  const N = S.length;
  const hMap = new Map();
  // Insert all characters with its
  // occurrence in the hash map
  insert(hMap, S, N);
  //Queries for sample input
  query2(hMap, 3, 6);
  query1(S, hMap, 5, 'z');
  query2(hMap, 1, 1);
  query1(S, hMap, 4, 'a');
  query1(S, hMap, 7, 'd');
  query2(hMap, 1, 7);
}
 
// Utility function to add the
// position of all characters
// of string into TreeSet
function insert(hMap, S, N) {
  for (let i = 0; i < N; i++) {
    const c = S.charCodeAt(i) - 97;
    if (!hMap.has(c)) {
      hMap.set(c, new Set());
    }
    hMap.get(c).add(i);
  }
}
 
// Utility function for update
// the character at position P
function query1(S, hMap, pos, c) {
  // We delete the position of the
  // previous character as new
  // character is to be replaced
  // at the same position.
  pos--;
  const previous = S.charCodeAt(pos) - 97;
  const current = c.charCodeAt(0) - 97;
  const chars = S.split('');
  chars[pos] = c;
  S = chars.join('');
  hMap.get(previous).delete(pos);
  if (!hMap.has(current)) {
    hMap.set(current, new Set());
  }
  hMap.get(current).add(pos);
}
 
// Utility function to determine
// number of different characters
// in given range.
function query2(hMap, L, R) {
  // Iterate over all 26 alphabets
  // and check if it is in given
  // range using floor() method.
  let count = 0;
  L--;
  R--;
  for (let i = 0; i < 26; i++) {
    if (hMap.has(i)) {
      const temp = Math.max(...Array.from(hMap.get(i)).filter(x => x <= R));
      if (temp >= L) {
        count++;
      }
    }
  }
  console.log(count);
}
 
main();

Output

3
1
5

Time complexity: O(Q * logN) where Q is number of queries and N is the size of the string.

Space complexity: O(NlogN), where N is the 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!