The first solution that comes to mind is to use use nested loops..But then we realize that it's a O(n^2) solution.
So we need to refine this solution. A better option than arrives to have an additional array that stores count of each character. This solution is better off than the previous one as it's running time has reduces to O(n). But this one consumes O(n) extra memory.
Can we do it in linear time with constant memory?
If yes, then how?
So we need to refine this solution. A better option than arrives to have an additional array that stores count of each character. This solution is better off than the previous one as it's running time has reduces to O(n). But this one consumes O(n) extra memory.
Can we do it in linear time with constant memory?
If yes, then how?
