AMAZON ONLINE ASSESMENT
Anonymous User
5559

You are given a string S of length N, Q ranges of the form [L, R] in a 2D array range, and a permutation arr containing numbers from 1 to N.
In one operation, you remove the first unremoved character as per the permutation. However, the positions of other characters will not change. Determine the minimum number of operations for the remaining string to be good.
NOTES:

  • A string is considered good if all the Q ranges have all distinct characters. Removed characters are not counted.
  • A range with all characters removed is considered to have all distinct characters.
  • The sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once
    1-based indexing is followed.

Example-1:

Given,
N = 5, Q = 2, S = "aaaaa"
arr = [2, 4, 1, 3, 5]
ranges = [[1,2],[4,5]]
Approach

  • After the first operation, the string becomes a_aaa
  • After the second operation, the string becomes a_a_a

Now, in both ranges, all characters are distinct.
Hence, the output is 2.

Example-2:
Given,

N = 8, Q = 3, S = "abbabaab"
arr = [6, 3, 5, 1, 4, 2, 7, 8]
ranges = [[1, 3], [4, 7], [3, 5]]
Approach

  • After the first operation, the string becomes abbab_ab
  • After the second operation, the string becomes ab_ab_ab
  • After the third operation, the string becomes ab_a__ab
  • After the fourth operation, the string becomes _b_a__ab
  • After the fifth operation, the string becomes _b____ab

Now, in all the ranges, all characters are distinct.
Hence, the output is 5.

Comments (10)