The time complexity of the above algorithm is O(D∗logD) where ‘D’ is the number of distinct characters in the input string. This means, in the worst case, when all characters are unique the time complexity of the algorithm will be O(N∗logN) where ‘N’ is the total number of characters in the string.
I think it should be N + DlogD in normal case because: the first loop to build map is iterating N items, so at least should have N complexity in final result? Can anyone explain?