Given two dimensional k x ((26^k)-1) array, containing every possible string of capital letters of length k, except one of them. How can we know the missing string while reading only theta(26^k) entries of the array, and not theta(k x (26^k)) entries?
We have thought of using 'k' pointers for all the 26^k columns, but it will still be the same as looking k x 26^k entries, we also considered checking for a[:0], a[:1], a[:2], . . . a[:(26^k)-1] but it is still the same as looking for k x 26^k values as slicing also counts as looking at those entries.
Here's a way to do it in Θ(26^k) time complexity by using an additional O(26^k) space.
Let's look at the intuition first -
(26^k)-1 entries. In the first row, all letters would have the same frequency except one whose frequency would be one lesser than the other 25. This letter would be the first letter of our missing string.26^(k-1) - 1 cols for which the corresponding first-row value was the missing letter.(but now in order to know which cols to look into we would need to store those cols somewhere else using additional space). And we would only have to look into 26^(k-1) - 1 entries in the second row.O(no. of entries) and constant space(26 letters). Once we know the missing letter in a given row, we can go through the row again and store indices of all the cols for which the letter is the missing letter and store those indices in a separate array using additional space O(26^(k-1-i)) for ith row.26^(k-2) - 1 entries for indices which we stored in our array when we looked at the 2nd row.So the total no. of entries we would have to look at in each row(after summing up the geometric series) would be -
sum{(26 - 1), (26^2 - 1), (26^3 - 1) ... (26^k -1)} = (26*(1 - (26^k))/(1-26) - k
which is Θ(26^k) time and space complexity.