Count Valid Pairs

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
2 upvotes
Asked in company
HSBC

Problem statement

Ninja has been learning about strings recently. While studying, he was fascinated by a pair of strings, say P and Q, in which every character in the first string, P, is less than the corresponding character in the second string, Q, i.e. P[i] < Q[i], where 0 <= 'i' < Length.

Now, he wants to count the number of such pairs of strings, of length 'N', which satisfies this rule.

Note: 
1. Strings contain only lower-case English alphabets.
2. Since the number of such pairs can be very large, return the answer modulo 10^9 + 7.

Example:

Let’s say length 'N' = 1. So, we’ll consider only the strings with length 1: “a”, “b”, “c”, ….., “z”. Now, If P = “a”, then Q can be “b”, “c”, “d”....., “z” (25 possibilities). If P = “b”, then Q can be “c”, “d”....., “z” (24 possibilities). And so on till P = “y”, then Q can be “z” (1 possibility).

Hence, the total number of pairs of strings that satisfy the given condition is: 25 + 24 + …… + 1 = 325.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ representing the number of test cases.

The first and the only line of every test case contains an integer ‘N’ representing the length of the pairs of strings to be found.
Output Format: 
For each test case, return the number of pairs of strings that satisfy the given condition.
Note: 
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100 
1 <= N <= 10^8

Where ‘N’ is the length of the pairs of strings to be found.

Time limit: 1 sec
Sample Input 1:
2
1
100
Sample Output 1:
325
34244837
Explanation for Sample Output 1:
In test case 1, refer to the example explained above.

In test case 2, similarly, we can calculate for the string of length 100 as above logic in test case 1 and we get total valid pairs as 34244837.
Sample Input 2:
2
2
1234567
Sample Output 2:
105625
198263616
Explanation for Sample Output 2:
In test case 1, we consider only the string of length 2: “aa”, “ab”,......, “az”, “ba”, “bb”, ……, “bz”,....., “zz”.

Now, if P = “aa”, then Q can be “bb”, “bc”,....., “bz”, “cb”, “cd”....., “zz” (625 possibilities).

Similarly, by calculating the number of possible pairs for the rest of the strings we get a total of 105625 possible pairs.

In test case 2, similarly, we can calculate for the string of length 1234567 as above logic in test case 1 and we get total valid pairs as 198263616.
Hint

Try generating all the possible strings of length N and then count the possible pairs.

Approaches (3)
Brute Force

A brute force approach could be to generate all the possible strings of length N and for each string, say P, we count the number of possible strings Q which satisfy the given condition. The idea is to start with an empty string and recursively append the characters to the string until we get a string of length 'N'. After generating a string, we iterate over it. For any character 'ch' present at index ‘i’ in the string ‘P’ (i.e. the generated string) ‘Q[i]' can store all the characters greater than ‘ch’ (using the given condition) i.e. 'COUNT' = ‘z’ - 'ch'.

 

Multiplying the count value for every index, gives us the number of possible strings Q, for the generated string, 'P'.

 

Now, repeat the above procedure for the rest of the strings. The sum of all the count of possible strings Q, for all the generated strings, gives us the final answer.

Time Complexity

O(26^N * N), Where ‘N’ is the length of strings.

 

Since we are generating all the possible strings of length N which takes O(26^N) time. For each string, we count the possible strings Q which takes O(N) time. Thus, the overall time complexity will be O(26^N * N).

Space Complexity

O(N), Where ‘N’ is the length of strings.

 

Since O(N) extra space is required for storing the generated string. Also, O(26) i.e. constant space is required by the recursion stack. Thus the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Count Valid Pairs
Full screen
Console