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

# 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.

Join the DZone community and get the full member experience.

Join For FreeMaintain 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!

Published at DZone with permission of Namit Sharma , DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

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

## {{ parent.tldr }}

## {{ parent.linkDescription }}

{{ parent.urlSource.name }}