Compare those strings solution codechef

Compare those strings solution codechef

 

Chef has two strings AA and BB consisting of lowercase alphabets, each of length NN. Help Chef in finding the number of indices ii (1iN)(1≤i≤N) such that A[iN]<B[iN]A[i…N]<B[i…N].

  • S[iN]S[i…N] denotes the suffix of string SS starting at index ii, i.e. SiSi+1SiSi+1  SNSN.
  • String S<S< String TT denotes that SS is lexicographically smaller than TT. If two strings SS and TT have the same length NN, we say that SS is lexicographically smaller than TT if there exists an index i(1iN)i(1≤i≤N) such that S1=T1,S1=T1, S2=T2,,Si1=Ti1S2=T2,…,Si−1=Ti−1 and Si<TiSi<Ti. For example, “abcabc” is lexicographically smaller than “acdacd“, “abeabe“, but not smaller than “abcabc“, “aacaac“. Compare those strings solution codechef

    CodeChef Starters 18 Division 3 (Rated) - CodeChef

Input Format

  • The first line contains TT denoting the number of test cases. Then the test cases follow.
  • The first line of each test case contains NN, denoting the length of the strings AA and BB.
  • The second line of each test case contains the string AA.
  • The third line of each test case contains the string BB.

Compare those strings solution codechef Output Format

For each test case, print a single line containing one integer – the number of indices ii such that A[iN]<B[iN]A[i…N]<B[i…N].

Constraints

  • 1T1051≤T≤105
  • 1N1061≤N≤106
  • The sum of NN over all test cases does not exceed 106106

Compare those strings solution codechef Sample Input 1 

2
2
ab
bb
3
aaa
aab

Sample Output 1 

1
3

Explanation Compare those strings solution codechef

Test Case 11:

  • For i=1i=1A[12]=A[1…2]= “abab“, B[12]=B[1…2]= “bbbb” and lexicographically, “abab” << “bbbb“.
  • For i=2i=2A[22]=A[2…2]= “bb“, B[22]=B[2…2]= “bb” and lexicographically, “bb” == “bb“.

Test Case 22: For each i{1,2,3}i∈{1,2,3}A[i3]<B[i3]A[i…3]<B[i…3].

Leave a Comment