10 hours ago

Rohit • 0

Hyderabad

Question 1: Maximize Product Operations

Problem Statement:

Given a string s, the "type" of the string is defined by its first and last characters. For example, if s = "babdcaac", the type is "bc" (starts with 'b' and ends with 'c').

You can perform operations on the string to reduce its size, where one operation is equal to removing one character from the ends (effectively yielding a contiguous substring of the original string). Your goal is to maximize the number of operations performed such that the resulting string has the same type as the original string s.

(Note: Maximizing the operations is equivalent to finding the minimum length contiguous substring that starts with s[0] and ends with s[n-1]).

Example:

s = "babdcaac"

Valid resulting strings of type "bc" and their operations:

• "babdcaac" (Length 8  Operations = 0)
• "bdcaac" (Length 6  Operations = 2)
• "babdc" (Length 5  Operations = 3)
• "bdc" (Length 3  Operations = 5)

The maximum number of operations performed to yield a valid string is 5.
 

Question 2: Distinct Characters Query

Problem Statement:

You are given a string data of lowercase English letters and a list of queries. There are two types of queries to process:

• Type 1: [1, pos, val] $\rightarrow$ Update the character at the 1-based index pos to the val-th lowercase English letter (e.g., 1 = 'a', 2 = 'b', ..., 8 = 'h').
• Type 2: [2, L, R] $\rightarrow$ Count and return the number of distinct characters present in the substring from 1-based index L to R.

Return an array containing the results of all Type 2 queries.

Example:

data = "abfdpbp"

queries = [[2, 3, 6], [1, 5, 8], [2, 1, 2], [1, 4, 1], [1, 7, 4], [2, 1, 7]]

1. [2, 3, 6]: Range "fdpb". Distinct characters: f, d, p, b. (Output: 4)
2. [1, 5, 8]: Update index 5 to 'h' (8th letter). String becomes "abfdhbp".
3. [2, 1, 2]: Range "ab". Distinct characters: a, b. (Output: 2)
4. [1, 4, 1]: Update index 4 to 'a'. String becomes "abfahbp".
5. [1, 7, 4]: Update index 7 to 'd'. String becomes "abfahbd".
6. [2, 1, 7]: Range "abfahbd". Distinct characters: a, b, f, h, d. (Output: 5)

Output: [4, 2, 5]