Question: Sprinklr | 18th October | Online Assessments | Smallest Common Substring | Substrings in substring

Entering edit mode

Average CTC: 20lpa

Company: Product based

Roles: Software Engineer, Software Developer

Question 1

Smallest Common Substring

You are given two strings A and B that are amde of lowercase English alphabets. Find the number of different pairs ((i,j),(k,l)) such that the substrings A[i.....j] and B[k.....l] are equal and the value of j-i+1 is minimum.

Example

Consider A = 'abc' and B = 'bcd'. You must determine the answer such that it meets the given conditions:

Let us choose a substring of length 1, those are 'b' and 'c'. The count is 2.
Let us choose a substring of length 2, which is 'bc'. The count is 1.

Since we need to minimize the length of matching substring hence the answer to the corresponding example is 2.

Function Description

Complete the solve function provided in the editor. This function takes the following 2 parameters

A: Represents the first string in the input.
B: Represents the second string in the input

Input Format

Note: This is the input format that you must use to provide custom input

The first line consists of a string denoting A
The second line consists of a string denoting B

Output

Print the number of different pairs ((i,j),(k,l)) such that the substrings A[i...j] and B[k...l] are equal and the value of j-i+1 is minimum.

Constraints

1<= |A|,|B|<=10^5

Sample Input

abdc
bd

Sample Output

Question 2

Click here to Practice

Substrings in substring

You are given a string S[1....n] of length n having only lowercase English letters.

You are also given q queries, each having two space-separated integers l and r.

For each query, you need to print the number of substrings of the string S[l...r] which starts and end with the same character.

Notes:

S[l...r] is a substring of S having a start index l and end index r.
A single character is also considered as a valid substring satisfying the above given condition.
Indexes start from 1. Same substrings starting at different indexes are considered different.

Example

Consider n=4, q=2, s=aabc. You must determine the cost of substring such that it meets the following conditions:

It must lie in [l,r]
starts and ends with the same character

for 1st query, l=1, r=2. We have 3 substring that satisfy the above condition, s[1,1], s[1,2], s[2,2].

for 2nd query, l=3, r=4. We have 2 substring that satisfy the above condition, s[3,3], s[4,4].

Function description

Complete the Sub_string_sol function provided in the editor. This function takes the following 4 parameters and returns the array of size q representing the number of required substring for each query:

n: Represents the length of the given string.
q: Represents the number of queries.
s: Represents the given string.
queries: q arrays one for each query, each contains two integers, l and r.

Input Format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button)

First line of the input will have two space-separated integers denoting the values of n and q respectively.
Second line of the input will have string S
In the next q lines, each line will have two space-separated integers l and r respectively.

Output Format

For every query, print the integer answer in the separate lines.

Constraints

1 <= n <= 10^4
1 <= q <= 10^5
1 <= l <= r <= n

Sample Input

Sample Output

ADD COMMENT • link

Entering edit mode

Solution to Problem 1

Analysis

Since it is required to minimise j-i+1, we can always choose i=j and hence we have to just determine the pairs of equal characters in the given strings. Thus we can find the count of each character in the given strings and the corresponding pairs will be count_in_string_1[char]*count_in_string_2[char]. We can add the pairs for each character to calculate the total pairs.

PseudoCode

solve(s,t):
     count1 = count2 = [0]*26
     for c in s:                             //counting the frequency of each character in s
           count1[c]++ 
     for c in t:                             //counting the frequency of each character in s
           count2[c]++
     ans = 0
     for c from 'a' to 'z':                  //total number of pairs is the sum of pairs for each character
           ans += count1[c]*count2[c]        //number of pairs for a given character is just the multiplication of the frequency of the character in two strings
     return ans

ADD COMMENT • link 2.2 years ago Ayush Gangwani 1.2k

Entering edit mode

Solution to Problem 2

Analysis

Let's first note that if there are x occurences of some character c in a string, the number of substrings that start and end with c are equal to x*(x+1)/2 (As there are x unit length substrings and C(x,2) other substrings, where C(x,2) = x*(x-1)/2). Thus we can determine the total number of required substrings if we know the frequency of each character.

To answer the queries efficiently, we can build a prefix sum array for each character to determine the frequency of the character in the specified range. We can then use the expression explained above to obtain the total number of required substrings. Thus each query is answered in O(w) where w is the alphabet size. The precomputation has a time complexity and space complexity of O(w*N) .

PseudoCode

solve(s,queries):
    n = len(s)
    pre[][] = int[n][26]                                   
    pre[0][s[0]-'a'] = 1                           //calculating the prefix sum for each character
    for i from 1 to n: 
        for c from 0 to 26:
            pre[i][c] = pre[i-1][c]
        pre[i][s[i]-'a']++

    ans = []
    for query in queries:
        current = 0 
        for c from 0 to 26:                       //to answer a query, we add the number of substrings for each character separately
            freq = pre[query.r] - pre[query.l-1]  
            current += (freq*(freq+1))/2          //As explained the number of substrings for a character with frequency freq is freq*(freq+1)/2 
        ans.append(current)
    return ans

ADD COMMENT • link 2.2 years ago Ayush Gangwani 1.2k