Member Avatar for tubby123

Hey is there a way to find the maximum occuring character in a string without using a hash map. ?
Maybe in dynamic Programming or something ???

  • 4 Contributors
  • 4 Replies
  • 118 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by mrnutty

Dani AI

Generated

asked for a way to get the most frequent character without using a hashmap. Responses so far: outlined a quadratic comparison approach, pointed to sorting-based solutions, and suggested counting by character codes for fixed alphabets. The right choice depends on alphabet size, memory limits, and whether a single element dominates the string.

A few practical Python options (tradeoffs noted):

# simple, very readable; worst-case O(n^2)
most = max(s, key=s.count)

Good for short strings or tiny alphabets. Avoid for long strings with many distinct characters because s.count scans the whole string repeatedly.

# majority (Boyer-Moore): O(n) time, O(1) extra memory,
# returns candidate only if an element appears > n/2; must verify.
def majority_candidate(s):
    cand, cnt = None, 0
    for ch in s:
        if cnt == 0:
            cand, cnt = ch, 1
        elif ch == cand:
            cnt += 1
        else:
            cnt -= 1
    return cand

Use this only when a majority is guaranteed or when a quick candidate+verification is acceptable.

# fixed-size counter for a known small charset (ASCII/bytes) — O(n)
counts = [0]*256
for ch in s:
    counts[ord(ch) % 256] += 1   # only safe for constrained input
most = chr(max(range(256), key=counts.__getitem__))

This is the fastest when the character domain is limited and known. It’s effectively what hinted at, but it fails for arbitrary Unicode without extra mapping.

Recommendation: if the input is arbitrary Unicode and using a hashmap/Counter is forbidden, either restrict/normalize the alphabet first, or sort the string in-place and scan runs (O(n log n)). If a strict majority is expected, use Boyer-Moore plus verification. If the domain is small (ASCII/bytes), use a fixed counter array for an O(n) solution with constant extra memory. Include an explicit tie-break rule (first occurrence, lexicographic, etc.) when equal frequencies matter.

Recommended Answers

All 4 Replies

Member Avatar for nmaillet

Does it need to be efficient? If O(n2) is acceptable, you could just initialize an int array of the same size, then store the number of following characters that are equal. Then use the index of the largest int value to locate your maximum occurring character.

Member Avatar for TrustyTony

You mean letter of highest frequency? I think sorting by counting and finding the maximum is equivalent problem if you are not dealing with unicode.

Member Avatar for tubby123

@tony : ya sorting in O(n logn) and then an O(n) for finding duplicates is a good one.
: good one too, but the int array is like a hash map right???
thnks for the responese guys..

Member Avatar for mrnutty

You can do this on O(n) using the fact that characters has a number associated with them. Here is live code

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.