PROBLEM LINKS:
Difficulty: Medium
Pre-requisite Knowledge:
- Basic Knowledge of Combinatorics
Core Idea/Tags:
Math, implementation
Time Complexity:
(O(Q*(K^2))) or (O(QK26))
Quick Explanation:
Store all characters of string in alphabetical order (a set preferred). Find total no of strings that can be generated, say N. Find the first letter of required string (for example, X = 1 to N/K, the string shall start with first letter in the set)
After finding the first letter, we need to length of answer string from X using combinatorics. Then, its just finding the required string by dictionary order. (Since the strings in a group are sorted).
(TIP: Now, the problem reduces to finding i-th string in dictionary order, which is merely basic math+implementation, since all strings to be considered are of same length. Thus, I strongly recommend the reader to give the problem a try at this point, before proceeding to read the “Detailed Explanantion”)
Detailed Explanation:
Store all characters of string in alphabetical order (a set preferred). Find total no of strings that can be generated, say N. (Let Pi be the mathematical operation "K permute i " where P is for no of permutations). Then,
N = \sum_{i=1}^{K} P_i
Now, for X = 1 to N/K, the string shall start with first letter; (N/K)+1 to 2*(N/K) with second letter and so on.
Pre compute the following values:
- Factorial value till K
- Pi value till K
- An array L of size K, where L[i] contains the number of possible strings of length i for a given/chosen first letter i.e., L[i]=\frac{P_{i+1}}{K}. This should be prefix summed so as to obtain the required ranges for string lengths. For example, for a string with 3 letters, L[3]={1,2,2}. On prefix summing it, its {1,3,5}. Thus, if X (after suitably choosing first letter}, belongs to interval {1,3], then the required string’s length is 2. And then we move on to find the remaining letters.
To find the remaining letters:
Since the first character and string length is known (say A), remaining (A-1) letters have to be chosen from pool of K-1 characters, and that has to be done in dictionary order. It is more of basic math and implementation. Many methods can be used, but that can be broadly classified into the following two approaches.
- Recursion (user “teja349” had used this - Link )
- Precomputation + Iteration (author’s solution uses this. Link below)
Explanation for Time Complexity:
While determining dictionary order, we needto keep track of used and ununsed characters. Further, we need to ensure we don’t use the already used ones. This can be implemented either by a hash array or by a set.
- Using Hash array - count variable (for length) and flag array to keep track of used (store 1) and unused (store 0). For choosing each character, we need to find which character to choose (math) and then traverse through all characters to find the i-th unused character (implementation).Thus, for K characters, time complexity is O(Q*K*26).
- Using set - insert all possible characters. Once a character is used, erase it from set (takes log(K)). So, the set contains only unused characters. For choosing each character, we need to find which character to choose (math) and then, traverse through set for the iterator to point at the required character. (takes K). Since K > log (K) , for each character, time complexity is K. Thus, final time complexity is O(Q*(K^2))