How to Determine the K^th character in the concatenated string

Question

Given a list that contains N strings of lowercase English alphabets. Any number of contiguous strings can be found together to form a new string. The grouping function accepts two integers X and Y and concatenates all strings between indices X and Y (inclusive) and returns a modified string in which the alphabets of the concatenated string are sorted.

You are asked Q questions each containing two integers L and R. Determine the $K^{th}$. character in the concatenated string if we pass L and R to the grouping function.

Input Format

• First Line: N(number of strings in the list)
• Next N lines: String $S_i$
• Next line Q(number of questions)
• Next Q lines : Three space-separated integers L, R and K

Output Format

• For each question, print the $K^{th}$ character of the concatenated string in a new line.

Sample Test Cases

Sample Input                 Sample Output

5                                 c
aaaaa                             d
bbbbb                             e
ccccc
ddddd
eeeee
3
3 3 3 
1 5 16
3 5 15

Explanation

• Q1 Grouped String - ccccc. 3rd character is c
• Q2 Grouped String - aaaaabbbbbcccccdddddeeeee. 16th character is d
• Q3 Grouped String - cccccdddddeeeee. 15th character is e

Note: It is always guaranteed that the $K^{th}$ position is valid

CONTEXT:

This question came up in a Hiring Challenge I did back in October. I just remembered this question and thought I'd have a go but I am still struggling with it.

There are no worked solutions online so I'm reaching out to this website as a final resort. Any help would be greatly appreciated. Thank you!

Answer 1

Let's say the input strings are stored in an array of strings named words. Build an N * 26 matrix to store the character count of each string. mat[i][0] will give count of a in words[i] and so on. This is preprocessing that only needs to be done once

    
    for(int i=0;i<words.size();i++){
        for(char ch : words[i]){
            mat[i][ch-'a']++;
        }
    }

Now for each query, call the function determine_character(). The logic behind iterating for each character in the range (l,r) is that after concatenation, the string we'll get is sorted.

char determine_character(vector<string> words, int l, int r, int k){    
    int sum=0;
    for(int i=0;i<26;i++){
         for(int j= l-1;j<=r-1;j++)
            sum += mat[j][i];
        
         if(sum>=k)
            return 'a' + i;    
    }
    return 'z';
}

Answer 2

Once you have understood the problem, the code itself is straightforward. Here, I'll demonstrate using R.

Let's start by defining S, the set of strings we are given:

S <- letters[1:5]
S <- paste0(S, S, S, S, S)
S
#> [1] "aaaaa" "bbbbb" "ccccc" "ddddd" "eeeee"

Now we can concatenate the Lth to the Rth string of a vector of strings, Str very easily by doing

concat <- function(Str, L, R) paste0(Str[L:R], collapse = "")

So, for example if we were given L = 1 and R = 2, we could do:

concat(S, 1, 2)
[1] "aaaaabbbbb"

Furthermore, we can find the character at position K of any string Str like this:

char_at <- function(Str, K) substr(Str, K, K)

So if we combine these two, we get:

f <- function(L, R, K) char_at(concat(S, L, R), K)

For example:

# Q1
f(3, 3, 3)
#> [1] "c"

# Q2
f(1, 5, 16)
#> [1] "d"

# Q3
f(3, 5, 15)
#> [1] "e"

Answer 3

I've used python3 to demonstrate the answer. Tried to comment as much as I can to make it self explanatory.

Repl: https://repl.it/@PavitraBehre/Kth-Character-in-Concatenated-String

#No of strings
n = int(input())

#Empty list to contain input strings
strings = []

#Looping N times, using _ as control variable as it's not needed anywhere
for _ in range(n):
  #Appending the stipped input string to lit
  strings.append(input().strip())

#Getting no of questions
q = int(input())

#Looping Q times
for _ in range(q):
  #Getting L,R,K as mapped tuples from input as int
  L,R,K = map(int, input().split())

  #Printing the L from Strings List
  #Note: lists use 0 based indexing and question has 1 based indexing
  print("L:", strings[L-1])

  #Printing the R from Strings List
  print("R:", strings[R-1])

  #Using List Splicing and join function to join the string
  #list[start:stop:step]
  #Splicing doesn't include the last index of stop value thus no R-1
  s = "".join(strings[L-1:R])
  print("L<->R: ", s)

  #Printing Kth Character (1 based indexing)
  print("K:", s[K-1])

Answer 4

I have tried to solve the problem using Python 3, this problem was asked in a HackerEarth assessment.

# Input code:
n = int(input())
arr = []
for _ in range(n):
    arr.append(input().strip())
p = int(input())
m = 3
Q = []
for _ in range(p):
    Q.append(list(map(int, input().split())))

out_ = solve(Q, arr)
print('\n'.join(out_))

Solution:

def solve(Q, arr):
    ans= [] # empty list to append the kth element for each Q
    for i in range(len(Q)): 
        L, R, K = Q[i] # We assign value to L, R, K
        # We join string from arr between index "L-1" and "R" (for zero indexing) and get element at Kth index (K-1)
        ans.append("".join(arr[L-1:R])[K-1])
    return ans

Answer 5

I have tried to solve the problem using JAVA, may you can improve the solution

private static char[] solve(int N, String[] str, int Q, int[][] query) {
       StringBuilder sb = new StringBuilder();
       char [] result = new char[Q];
       int q_count=0;
       while(Q>0){
           for(int i=query[q_count][0]-1; i <= query[q_count][1]-1; i++){
               sb.append(str[i]);
           }
           char [] ta = sb.toString().toCharArray();
           Arrays.sort(ta);
           result[q_count]= ta[query[q_count][2]-1];
           q_count++;
           sb.delete(0, sb.length());
           Q--;
       }
       return result;
    }

Answer 6

 public  static  char[]  solve(int [] [] Q , String[] arr) {

    char[] [] mat = new char[arr.length][26];
    for(int i=0;i<arr.length;i++){
        for(char ch : arr[i].toCharArray()){
            mat[i][ch-'a']++;
        }
    }
    for ( int i =1; i <mat.length; i++){
        for ( int j=0; j< mat[0].length ; j++){
            mat[i][j] =  (char) ( mat[i][j] + mat[i-1][j] );
        }
    }
    char [] result = new char[Q.length];

    for(int i=0;i<Q.length;i++){
        result[i] = determineCharacter2(Q[i][0], Q[i][1], Q[i][2], mat);
    }


    return  result;

}

static char determineCharacter2(int l, int r, int k, char[] [] mat){
    int sum=0;
    for(int i=0;i<26;i++){
            if ( l==1){
                sum =sum + mat[r-1][i];
            }else{
                sum =sum + mat[r-1][i] - mat[l-2][i];
            }

        if(sum>=k)
            return  (char)  ( 'a' + i );
    }
    return 'z';
}