48. Find Duplicate Characters in a String

Given a string s of lowercase letters, find every character that occurs more than once. Print each such character with its count as 'char:count', sorted alphabetically by character, space-separated. If there are no duplicate characters, print 'None'.

Input: The input is a single line containing a string s of lowercase letters. Output: Print each duplicated character as 'char:count', sorted alphabetically and space-separated, or print 'None' if there are no duplicates.

1 <= |s| <= 10^5

Because the alphabet size here is fixed and small (26 lowercase letters), a plain array is a far simpler and faster choice than a general-purpose hash map - a useful reminder that hash maps aren't always the best tool.

Find every letter that appears more than once in a string, and report each one with exactly how many times it occurred. Brute force: For every character, scan the rest of the string directly counting its occurrences - this costs O(n²), wasteful when a single counting pass does the job. Optimised: A single pass building a frequency array (sized just 26, since only lowercase letters are involved) counts everything at once in O(n) - then a simple, fixed 26-step walk over the alphabet produces the answer already in sorted order, with no separate sorting step needed.

For each character in the string, scan the rest of the string to count how many times it occurs in total, taking care to only report each distinct character once (e.g. only counting it the first time it's encountered, to avoid reporting the same duplicate character multiple times). This directly answers the question of which characters repeat and how often, but comparing every character against every other character makes it quadratic in the length of the string. Time: O(n^2) Space: O(1) extra (excluding output)

Sort a copy of the string's characters, which brings every occurrence of the same character next to each other. Then make a single linear scan over the sorted characters, measuring the length of each consecutive run of identical characters; any run of length 2 or more is a duplicate, and its length is its count. Because sorting already groups and orders the characters, printing the duplicates found this way comes out alphabetically ordered for free, and it avoids the quadratic all-pairs comparison of the brute force. Time: O(n log n) Space: O(n)

Since the string only contains lowercase English letters, allocate a fixed array of exactly 26 counters and make one linear pass over the string, incrementing the counter for each character's letter. Then iterate over the 26 letters in order from 'a' to 'z', printing any letter whose count is 2 or more together with its count - since this iteration is already over the alphabet in order, the output comes out sorted alphabetically without any actual sorting step. This does the minimum possible single pass over the input and uses only constant extra space, since 26 is a fixed bound independent of the string's length. Time: O(n) Space: O(1)

1. Count how many times each of the 26 lowercase letters appears, using a small fixed-size array (one slot per letter). 2. Walk the alphabet from a to z in order. 3. For every letter with a count greater than 1, print it alongside its count.

Time: O(n) - one pass to count, plus a fixed 26-step walk to report, which is effectively O(1) extra on top of the counting pass. Space: O(1) - the frequency array is always exactly 26 slots, regardless of the input string's length.

A string with no repeated characters at all ('None'); a string where every character is identical (a single output pair with a large count); s up to 10^5 characters for performance.

Walking the alphabet a-z (rather than the string's own character order) to produce the output is what gives you sorted results 'for free' - a small but elegant trick worth pointing out explicitly.