I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

# Thursday Code Puzzler: Second Highest Frequency

07.18.2013
| 6697 views |

It's Thursday, so it's time for another code puzzler. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Calculate The Second Highest Frequency

Write a method that accepts a String and returns the  character with the second highest frequency. For example "aabbbc" would return 'a'. If the string contains spaces, they can be disregarded from the count.

Catch up on all our previous puzzlers here

Tags:

### Milind Deo replied on Thu, 2013/07/18 - 6:32am

```import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/**
*
* @author milind
*/
public class SecondHighestFrequency {

private Map<Character, Character> charMap;
private Map<Character, Integer> countMap;

public SecondHighestFrequency() {
super();
this.charMap = new HashMap<Character, Character>();
this.countMap = new HashMap<Character, Integer>();
}

public static void main(String[] args) {
String str = "abccaaccdd";
new SecondHighestFrequency().findSecondHighestFrequecny(str);

}

/**
* This is the method which will found out duplicate character and add the
* count in the string
*
* @param str
*/
public void findSecondHighestFrequecny(String str) {

char charArrr[] = str.toCharArray();
for (int i = 0; i < charArrr.length; i++) {
char ch = charArrr[i];
if(ch !=' '){
if (this.charMap.get(new Character(ch)) == null) {
this.charMap.put(new Character(ch), new Character(ch));
} else {
// If Duplicate try to get the coun value from Map
Integer count = this.countMap.get(new Character(ch));
if (count == null) {
this.countMap.put(new Character(ch), new Integer(2));
} else {
this.countMap.put(new Character(ch), count+1);
}
}
}
}
// Now Sort the count Map
MapValueComparator comp = new MapValueComparator(countMap);
TreeMap<Character, Integer> treeMap =
new TreeMap<Character, Integer>(comp);
treeMap.putAll(countMap);
if(treeMap.size() >=2) {
System.out.println("Second Highest value :"+
treeMap.entrySet().toArray()[1]);
}else{
System.out.println(" There is no Second Value only one "
+ "value present");
}
}
}
/**
* Comparator
* @author milind
*
*/
class MapValueComparator implements Comparator<Character> {

Map<Character, Integer> original;
public MapValueComparator(Map<Character, Integer> original) {
this.original = original;
}
public int compare(Character a, Character b) {
if (original.get(a) >= original.get(b)) {
return -1;
} else {
return 1;
}
}
}```

### Andreas Schilling replied on Thu, 2013/07/18 - 7:55am

Here's my solution with some guava magic. Most awesome library ever :-)

```import java.util.Collection;
import java.util.List;

import junit.framework.Assert;

import org.junit.Test;

/**
*
* @author aschilling
*/
public class TestCountCharacters
{
@Test
public void testSecondHighestFrequency()
{
Assert.assertEquals( 'a', secondHighestFrequence( "aabbbc" ).charValue() );
Assert.assertEquals( 'b', secondHighestFrequence( "aaaabbbc" ).charValue() );
Assert.assertEquals( 'c', secondHighestFrequence( "abcc  aaaaccdd" ).charValue() );
Assert.assertNull( secondHighestFrequence( "aa" ) );
}

private Character secondHighestFrequence( final String input )
{
final Multimap<Character, Character> bins =
Multimaps.index(
Chars.asList( CharMatcher.isNot( ' ' ).retainFrom( input )
.toCharArray() ), Functions.<Character> identity() );
final Function<Collection<Character>, Integer> collectionToSize =
new Function<Collection<Character>, Integer>()
{
@Override
public Integer apply( final Collection<Character> collection )
{
return collection.size();
}
};

final Function<Character, Integer> collectionSize =
Functions.compose( collectionToSize, Functions.forMap( bins.asMap() ) );
final List<Character> twoMostFrequent =
Ordering.natural().onResultOf( collectionSize ).greatestOf( bins.keySet(), 2 );
return twoMostFrequent.size() == 2 ? twoMostFrequent.get( 1 ) : null;
}
}```

### sun east replied on Thu, 2013/07/18 - 8:07am

```scala>
scala> def second(str: String): Char = {
|   val ord = str.groupBy(identity).toSeq.sortBy{ case(c,s) => -s.size }
|   ord(1)._1
| }
second: (str: String)Char

scala> second("aabbbc")
res0: Char = a```

### Luka Matosevic replied on Thu, 2013/07/18 - 8:45am in response to: sun east

```import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class CharUtil {

public static Character findSecondHighestFrequency(final CharSequence seq) {
Character result = null;

// Build char count map
final Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < seq.length(); ++i) {
final char c = seq.charAt(i);
if (c != ' ') {
Integer count = map.get(c);
map.put(c, count != null ? ++count : 0);
}
}

// At least 2 entries ?
if (map.size() >= 2) {
final List<Entry<Character, Integer>> entries =
new ArrayList<>(map.entrySet());
Collections.sort(entries,
new Comparator<Entry<Character, Integer>>() {
@Override
public int compare(final Entry<Character, Integer> e1,
final Entry<Character, Integer> e2) {
return e2.getValue().compareTo(e1.getValue());
}
});

// Second highest is the second enttry
result = entries.get(1).getKey();
}

return result;
}

public static void main(final String... args) {
final Character c = CharUtil.findSecondHighestFrequency("aabbbc");
}
}
```

### Star Duster replied on Thu, 2013/07/18 - 4:44pm

No solution cares about the highest frequency appearing twice so how about: 'aaaabbbbcccd'
What is the Second Highest Frequency then?
I would expect 'c'

All current approaches return only one solution but how about: 'aaaabbbcccd'
What is the Second Highest Frequency then?
I would expect 'b' and 'c'

### Adam Tankanow replied on Fri, 2013/07/19 - 9:40am

Throwing Clojure into the mix (this solution also addressed Star Duster's comment):

```(defn second-highest-frequency
[^String unsorted-string]
(->> unsorted-string
sort
(partition-by identity)
(group-by count)
(into (sorted-map-by >))
second
val
(mapcat distinct)))
```
Calling this at the REPL yields:
```user=> (second-highest-frequency "aabbbc")
(\a)
user=> (second-highest-frequency "aabbbcccaa")
(\b \c)
```

### Alexey Kutuzov replied on Fri, 2013/07/19 - 10:55am

Something like that:

```public class Test {
public static char findSecond(String str) {
char firstMax = 127, secondMax = 127;
long[] freq = new long[128];
for (char c : str.toCharArray()) {
long curr = ++freq[c];
if (curr > freq[firstMax]) {
secondMax = firstMax;
firstMax = c;
}
}
return secondMax != 127 ? secondMax : firstMax;
}

public static void main(String[] args) {
System.out.println(findSecond("aabbbcccc"));
}
}
```

It works for ascii only but has O(str.length) and use fixed mem size for any case.

### Alexey Kutuzov replied on Fri, 2013/07/19 - 2:21pm in response to: Alexey Kutuzov

Actually there should be one more condition to check if curr greater than freq[secondMax] value. Without that it will lost case like "aaabbbbbbcccc".

### David Whatever replied on Sun, 2013/08/11 - 10:53pm

I decided to try to use Java 8 lambdas again, although I suspect I'm doing some of this in a more difficult fashion than I need to.

Edit: I was hoping to get comments on this, as my plan is to use this as a live demo for a tutorial on Java 8 features which I plan to give in a bit. That said, I revised my earlier entry to have a bit better style, and comments for each step of the way:

```public class Final {
public static void main(String[] args) {
if(args.length != 1) {
System.err.println("Usage:");
System.err.println("{app} \"<string to evaluate>\"");
return;
}

// First we convert to a Map of character to occurance count
// Then, we convert to a TreeMap of occurance count to list of characters
TreeMap<Long, List<Character>> frequency = args[0]
.chars()                            // with the characters in an Intstream
.filter(Character::isLetterOrDigit) // filter out non letter/digit chars
.map(Character::toUpperCase)        // and convert to upper-case
.boxed()                            // convert to Stream<Integer>
.collect(                           // collect results
groupingBy(                       // grouped into a map
(i)->(char)(int)i,              // with key being identity (plus, cast Integer back to Character)
counting()                      // and with a count for how many times we see each key
)
)
.entrySet()                         // then, take the entries in that map
.stream()                           // and as a Stream<Map.Entry<Character, Long>>
.collect(                           // collect results
groupingBy(                       // grouped by
Map.Entry::getValue,            // entry value (occurance count)
TreeMap::new,                   // into a SortedMap (tree map)
mapping(                        // mapping the entries
Map.Entry::getKey,            // by entry key
toList()                      // into a list
)
)
);

Map.Entry<Long, List<Character>> highestCount = frequency.pollLastEntry();
Map.Entry<Long, List<Character>> secondHighestCount = frequency.pollLastEntry();
if (highestCount == null) {
System.out.println("No usable characters appeared in the input string");
return;
}
System.out.println("Character(s) with the highest entry count of " + highestCount.getKey() + ": " + highestCount.getValue());

if (secondHighestCount != null)
System.out.println("Character(s) with the second highest entry count of " + secondHighestCount.getKey() + ": " + secondHighestCount.getValue());
else
System.out.println("There was no second-highest entry count; acceptable characters occurred equally");
}```

### sun east replied on Fri, 2013/07/19 - 6:53pm in response to: Star Duster

Fair enough.

```scala>
scala> def second[A](xs: Seq[A]): Set[A] = {
|   val dict = xs.groupBy(identity).groupBy(_._2.size)
|   val freq = dict.keys.toSeq.sorted
|   if(freq.size < 2) Set()
|   else dict(freq(freq.size-2)).keySet
| }
second: [A](xs: Seq[A])Set[A]

scala> second("")
res0: Set[Char] = Set()

scala> second("abbccc")
res1: Set[Char] = Set(b)

scala> second("aabbbcccaa")
res2: Set[Char] = Set(b, c)

scala> second(Array(1,1,1,2,2,3,3,4,4,5,6,6,6,6))
res3: Set[Int] = Set(1)

scala> second(Array(1,1,1,2,2,3,3,4,4,5,6))
res4: Set[Int] = Set(2, 3, 4)```

### matt inger replied on Fri, 2013/07/19 - 10:06pm in response to: sun east

I can up with something very similar, though i did the keyset up front:

```  def nthHighest(s:String,i:Int) : Set[Char] = {
val dict = s.toList.groupBy(identity).groupBy(_._2.size).mapValues(_.keySet).toList.sortBy(_._1).reverse
if (dict.size > i)
dict(i)._2
else
Set()
}```

I'm still somewhat new to scala, but i live it's expressiveness.  Notice how most of the java solutions (even with the lambas) are so much more verbose.

### Kamal Mettananda replied on Wed, 2013/07/24 - 1:35am

I decided to try this puzzle with a test driven approach and wrote initial test cases  followed by the support for multiples of same frequencies. Below is one of the completed code.

```package com.digizol.puzzle;

import java.util.*;

public class SortBasedFrequentCharacters {

public char[] getSecondMostFrequent(String text) {

char[] charArray = text.toCharArray();
Arrays.sort(charArray);

List<Frequency> list = new ArrayList<Frequency>();
char previous = '\u0000';
Frequency f = null;

for (int i = 0; i < charArray.length; i++) {
char c = charArray[i];

if (i == 0 || previous != c) {
f = new Frequency(1, c);
previous = c;
} else {
f.count += 1;
}
}

Collections.sort(
list,
new Comparator<Frequency>() {
public int compare(Frequency fr0, Frequency fr1) {
// sort in descending order
return fr1.count - fr0.count;
}
}
);

// supporting multiple characters being most frequent

int currentFrequency = 0;
boolean secondMostFound = false;
int start = -1;
int end = -1;
for (int i = 0; i < list.size(); i++) {
Frequency frequency = list.get(i);
if (i == 0) {
currentFrequency = frequency.count;
} else if (currentFrequency != frequency.count) {
if (secondMostFound) {
end = i;
break;
} else {
secondMostFound = true;
start = i;
end = i;
}
}
}

char values[] = null;
if (secondMostFound) {
List<Frequency> secondMostFrequencies = list
.subList(start, end + 1);
values = new char[secondMostFrequencies.size()];
for (int i = 0; i < secondMostFrequencies.size(); i++) {
values[i] = secondMostFrequencies.get(i).character;
}
} else {
values = new char[0];
}
return values;
}

private class Frequency {
int count;
char character;

public Frequency(int count, char character) {
this.count = count;
this.character = character;
}
}
}```

Final test cases are as follows.

```package com.digizol.puzzle;

import static java.lang.Character.valueOf;
import static org.junit.Assert.assertEquals;
import java.util.*;
import org.junit.*;

public class SecondFrequentCharactersTest {

private MapBasedFrequentCharacters sut;

@Before
public void setup() {
sut = new MapBasedFrequentCharacters();
// sut = new SortBasedFrequentCharacters();
}

@Test
public void shouldReturnCorrectWhenManyMostFrequentsAndOneSecondMostFrequent() {
// both i & c are the most frequent, y is the second most frequent
assertEquals(valueOf('y'),
valueOf(sut.getSecondMostFrequent("iiixiiyycbcccc")[0]));
}

@Test
public void shouldReturnCorrectWhenManyMostFrequentsAndManySecondMostFrequents() {
// both i & c are the most frequent, x & y are the second most frequent
char[] secondMostFrequents = sut.getSecondMostFrequent("iiixxiiyycbcccc");
assertEquals(2, secondMostFrequents.length);

List<Character> expected = new ArrayList<Character>();
for (int i = 0; i < secondMostFrequents.length; i++) {
expected.remove(Character.valueOf(secondMostFrequents[i]));
}
assertEquals(0, expected.size());
}

// previous test cases are modified as below

@Test
public void shouldReturnNullForEmptyText() {
assertEquals(0, sut.getSecondMostFrequent("").length);
}

@Test
public void shouldReturnNullForTextOfSameCharacter() {
assertEquals(0, sut.getSecondMostFrequent("dddddddd").length);
}

@Test
public void shouldReturnCorrectCharWhenTextHasTwoCharsOneBeingMostFrequent() {
assertEquals(valueOf('y'), valueOf(sut.getSecondMostFrequent("iiiiiyiiiii")[0]));
}

@Test
public void shouldReturnCorrectOneForATextWithOneBeingSecondMostFrequent() {
// most frequent is 'i', second most is 'd'
assertEquals(valueOf('d'),
valueOf(sut.getSecondMostFrequent("iaibicidieidif")[0]));
}
}```

### Edo Kan replied on Wed, 2013/07/24 - 6:27am

```"aabbbc"
.ToCharArray()
.GroupBy(c => c)
.OrderByDescending(g => g.Count())
.Skip(1)
.Take(1)
.Select(g => g.Key)
.First()
```

### Artur Biesiadowski replied on Wed, 2013/07/24 - 7:53am

```Xtend + Guava

```
`val letters = HashMultiset.create("aaabbbbcc".toCharArray)`
```val freq = letters.elementSet.sortBy[letters.count(it)].reverseView
```
```println(if ( freq.size > 1) freq.get(1) else "");
```

### Mike Hostetler replied on Wed, 2013/07/24 - 10:11am

How come no one put a Python version in yet?

```class Freq(object):

def find_second(self, my_str):

chars_map= {}

for ch in [x for x in my_str if x!=" "]:

count = chars_map.get(ch,0)
count+=1

chars_map[ch]=count

char_count = [(x,chars_map[x]) for x in chars_map]

if len(char_count)<2:
return char_count[0][0]

char_count = sorted(char_count,key=lambda x: x[1])

return char_count[-2][0]

```

### George Dernikos replied on Wed, 2013/07/24 - 10:14am

```"aabbbc".ToCharArray()
|> Array.toSeq
|> Seq.countBy id
|> Seq.sortBy (snd >> (~-))
|> Seq.skip 1
|> Seq.take 1
|> Seq.exactlyOne
|> fst
```

### Robert Kimble replied on Wed, 2013/07/24 - 10:27am in response to: Mike Hostetler

Here's my Python (2.7) version:

```from collections import Counter
def second_highest(s_input):
return Counter(''.join(sorted(s_input)).strip() ).most_common(2)[1][0]```

### Leandro Santos replied on Wed, 2013/07/24 - 10:42am

Ruby solution.
```require 'minitest/autorun'

class SecondHighestFrequencyFinder
def findFromString(s)
m = s.chars.inject({}) {|h,c| h[c] = s.count(c);h }

min = m.values.min
max = m.values.max

m.find {|k,v| v < max && v > min }.first
end
end

class TestSecondHighestFrequencyFinder < MiniTest::Unit::TestCase
def	setup
@finder = SecondHighestFrequencyFinder.new
end

def test_find_from_string
assert_equal 'b', @finder.findFromString('aaaaaabbbbccc')
assert_equal 'a', @finder.findFromString('aaabbbbcc')
end
end
```

### Artur Biesiadowski replied on Wed, 2013/07/24 - 11:45am in response to: Leandro Santos

@Leandro Santos
Is m sorted? If not, how do you know that you will get second highest frequency, not just random one from the middle?
What about having just 2 distinct letters in string?

### Leandro Santos replied on Wed, 2013/07/24 - 1:23pm in response to: Artur Biesiadowski

Can you show me what you mean with a test string? It's hard to discuss it without having a test case scenario.

### Artur Biesiadowski replied on Wed, 2013/07/24 - 3:16pm in response to: Leandro Santos

@Leandro

Try

"aaabbbb" - will expect a to be an answer, but I think your program will show nothing.

"aaaabccddeeffgghhhiijjkkllmmnnoopp" - h is expected answer, but I think that your program will show one of random letters other than a or b.

### Leandro Santos replied on Thu, 2013/07/25 - 10:55am in response to: Artur Biesiadowski

@Artur

This should fix the issue, albeit it is a bit of a brute force solution. I updated the tests to reflect your scenarios.

```require 'minitest/autorun'

class SecondHighestFrequencyFinder
def findFromString(s)
m = s.chars.inject({}) {|h,c| h[c] = s.count(c);h }

suv = m.values
max = suv.max
target = suv.find_all {|n| n < max}.max

tuple = m.find {|k,v| v == target }
tuple.first if tuple
end
end

class TestSecondHighestFrequencyFinder < MiniTest::Unit::TestCase
def	setup
@finder = SecondHighestFrequencyFinder.new
end

def test_find_from_string
assert_equal 'b', @finder.findFromString('aaaaaabbbbccc')
assert_equal 'a', @finder.findFromString('aaabbbbcc')
assert_equal nil, @finder.findFromString('aabb')
assert_equal 'a', @finder.findFromString('aaabbbb')
assert_equal 'h', @finder.findFromString('aaaabccddeeffgghhhiijjkkllmmnnoopp')
end
end
```

### Leonardo Goslar Otto replied on Fri, 2013/08/16 - 3:27pm

In Brazilian portuguese.
Java solution using TDD: http://blog.rocktto.com/2013/08/quebra-cabeca-dzone-segunda-maior-frequencia/