Problem link
Difficulty
EASY - MEDIUM
Pre-requisites
two pointers, binary search
Problem
Find number of sub-matrices of a matrix of dimension n * n having exactly K distinct characters from English lower case alphabet.
Solution
Brute Force won’t pass
If for each sub-matrix, we count number of distinct characters in it using O(R * C) where R is number of rows and C is number of columns in matrix. It’s time complexity will be O(n 6) which is too slow.
Fix a particular Height
Fix a height, then try for each 1 <= i <= j <= n such that you are currently looking at row = height and columns from i to j(inclusive). Now for this fixed i, j, you can note that if we iterate over k >= height such that we are currently looking at rectangle (height, i) and (k, j). Then in this rectangle, if we increase k, then number of distinct elements also increase. So you can apply two binary searches over k to solve problem for fixed, height, i and j. So overall complexity will be O(n * n * n * n * log n).
More optimizations
By using the idea, that k will always increase, you can solve it in O(n^4). This idea is called two pointers idea.
You can also use a solution called monotone queue too.
Another solution
It uses trick that K is not that large, K <= 26. So you can use bit-mask idea to solve the problem too.
Tester’s solution:
You can access it here.