Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

# O(n^2) vs O(n) Techniques for Finding the Max Count of a Digit in the Given Numerical String

### Let's look at a couple of techniques for finding the max count of a certain digit in a string and see how complex or simple our solutions are.

· Performance Zone ·
Free Resource

Comment (4)

Save
{{ articles[0].views | formatCount}} Views

Sensu is an open source monitoring event pipeline. Try it today.

Hello, Buddies. I came across this question related to Java String handling, so I thought of sharing it .

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

For a complete solution, refer to the Answer:

The first approach is 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? A solution with O(n) complexity, i.e. having a lookup array.

Answer: 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.

Happy coding! Check out the repo at this link.

Topics:
performance ,java ,arrays ,tutorial

Comment (4)

Save
{{ articles[0].views | formatCount}} Views

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.