O(n^2) vs O(n) techniques for finding the max count of a digit in the given numerical String.

Hello Buddies

Came across this question related Java String handling, so thought of sharing.

Question:
Given a string made up of n number of digits, find the digit having the maximum number of occurrence.
Eg. "12333123654"
Here, 3 is the digit being repeated for the maximum number of times.

Answer:
First approach can be to scan the string as a character array, maintain a map that can update the occurrence count. In the end find the max value and then the corresponding key.


Question:
What is the complexity of this solution?

Answer:
O(n^2) since we are iterating and using contains check.


Question:
Any better approach?

Answer:
Solution with O(n) complexity, i.e. having a lookup array.
We have digits 0 to 9, which can be related to each index of an array. For the values, update the occurrence count in the values.

For complete solution, refer to this link.

Happy Coding!!