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

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

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

Maintain Application Performance with real-time monitoring and instrumentation for any application. Learn More!

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.

Collect, analyze, and visualize performance data from mobile to mainframe with AutoPilot APM. Learn More!

Topics:
performance ,java ,arrays ,tutorial

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}