[Part 2] Finding Second Highest Frequent Characters using Java

With Java, finding character frequency in a text is a popular problem. When multiple characters got same frequency, it becomes interesting.

Initial part of finding second highest frequency characters in a text was discussed previously and covered the scenarios where a single character is the most frequent. Since this is the continuation post of that, I strongly recommend you to read the first part before this. The intention of this second post is to cover the scenarios at which the previous program failed, specifically the scenarios where multiple characters are of the same frequencies.

Part 1: The requirement is to return the character that is the second most frequent. Before writing any code, it is important to break down this requirement into a simple set of test cases.
The requirement of Part 2 is to return the characters those are the second most frequent. Before writing any code, it is important to break down this requirement into a simple set of test cases.

Previous production codes can return only one character as the second most frequent. If there are multiple characters matching the criteria, the return type of the code most be modified to a character array. Along with that change, all the previous test cases must be modified to support the returned character array. When there are no matches, it is better to expect the code to return an empty array rather than null, so the test cases has to be modified to reflect that.

Similar to the previous post, new test cases are identified prior to writing any implementation code. While supporting these multiple character scenarios, both map based and sorting based programs are modified to satisfy the test cases. You can find those below in this post.

New Test Cases

1. shouldReturnCorrectWhenManyMostFrequentsAndOneSecondMostFrequent()
    > result should be this second most frequent character
2. shouldReturnCorrectWhenManyMostFrequentsAndManySecondMostFrequents()
    > result should be these second most frequent characters

Above two test cases along with the modified previous test cases are written 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>();
        expected.add('x');
        expected.add('y');
        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])
                    );
    }
}

Production Code

Similar to previous post, map based solution is modified first followed by the sorting based one to satisfy all above test cases.

Map based solution

Previous map based solution had the character frequencies recorded in the map. At the 'second most frequent character' finding logic, two 'char' variables were used. With the new scenarios there are be multiple characters for both most frequents and second most frequents, so the char variables can be replaced with two lists as shown below.
package com.digizol.puzzle;

import java.util.*;
import java.util.Map.Entry;

public class MapBasedFrequentCharacters {

    public char[] getSecondMostFrequent(String text) {

        char[] charArray = text.toCharArray();

        // calculate char frequencies
        Map<Character, Integer> charFrequenciesMap 
                                      = new HashMap<Character, Integer>();

        // loop1
        for (char c : charArray) {
            int frequency = 1;
            if (charFrequenciesMap.get(c) != null) {
                frequency = charFrequenciesMap.get(c) + 1;
            }
            charFrequenciesMap.put(c, frequency);
        }

        int currentMostFrequency = 0;
        int currentSecondMostFrequency = 0;
        List<Character> mostFrequentChars = new ArrayList<Character>();
        List<Character> secondMostChars = new ArrayList<Character>();

        // find second most frequent char
        Iterator<Entry<Character, Integer>> charFrequencies 
                               = charFrequenciesMap.entrySet().iterator();

        // loop2
        while (charFrequencies.hasNext()) {
            Entry<Character, Integer> entry = charFrequencies.next();

            char currentChar = entry.getKey();
            int frequency = entry.getValue();

            if (frequency > currentMostFrequency) {
                secondMostChars.clear();
                secondMostChars.addAll(mostFrequentChars);
                mostFrequentChars.clear();
                mostFrequentChars.add(currentChar);
                currentSecondMostFrequency = currentMostFrequency;
                currentMostFrequency = frequency;
            } else if (frequency == currentMostFrequency) {
                mostFrequentChars.add(currentChar);
            } else if (frequency > currentSecondMostFrequency) {
                secondMostChars.clear();
                secondMostChars.add(currentChar);
                currentSecondMostFrequency = frequency;
            } else if (frequency == currentSecondMostFrequency) {
                secondMostChars.add(currentChar);
            }
        }

        char[] result = new char[secondMostChars.size()];
        for (int i = 0; i < secondMostChars.size(); i++) {
            result[i] = secondMostChars.get(i);
        }

        return result;
    }
}

Sorting based solution

Previous sorting based solution had sorted the list of 'Frequency' in the descending order of frequencies; and returned the second element in the list for the second most frequent. However with the new scenarios, there can be multiple most frequent characters so the second element may contain another most frequent character. Similarly, there can be multiple 'second most frequent' elements in the list. Java Comparator is used to sort the frequency data in this program. It is required to traverse through the list from the start and extract an array of elements with the second most frequency. Following is the modified program.
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);
                list.add(f);
                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;
        }
    }
}

In summary, the puzzle can be solved in many ways as shown in this series of articles. One important point to note is the use of test cases to identify the scenarios before any production code. As you may have already noticed, the same set of test cases were used to test two different implementations. If you have noticed any scenarios that are not covered here, please let me know via comments section so that I can address those.

COMMENTS

BLOGGER
Name

About,2,Adsense,3,Ant,1,Apache,3,Axis,3,Blogger,1,Books,1,CentOS,2,Chrome,2,CSS,2,Database,3,Earn Online,3,Eclipse,10,Facebook,1,Firefox,10,Gmail,4,GNU/Linux,9,Google,26,GWT,8,Hardware,2,IE,5,Interesting,15,Internet,14,Java,49,Javascript,7,JBoss,1,Jenkins,1,Log4j,2,Me,6,Microsoft,2,Miscellaneous,1,News,11,Opinion,10,OSGi,1,PHP,1,Productivity,3,Programming,36,Puzzle,3,Security,4,Software,41,Sports,9,Spring,2,Story,6,Subversion,3,TDD,4,Tech,2,Tips,1,Tomcat,6,Tutorial,13,Ubuntu,4,Web application,14,Web Design,2,Web services,3,Windows,10,Yahoo,1,Zip,2,
ltr
item
Digizol: [Part 2] Finding Second Highest Frequent Characters using Java
[Part 2] Finding Second Highest Frequent Characters using Java
With Java, finding character frequency in a text is a popular problem. When multiple characters got same frequency, it becomes interesting.
https://3.bp.blogspot.com/-5_kI3QIQKqE/Uevlinwiu_I/AAAAAAAAAyA/u_I7mhBUhjg/s1600/Letters-Frequency.jpg
https://3.bp.blogspot.com/-5_kI3QIQKqE/Uevlinwiu_I/AAAAAAAAAyA/u_I7mhBUhjg/s72-c/Letters-Frequency.jpg
Digizol
https://www.digizol.com/2013/07/second-highest-frequency-characters.html
https://www.digizol.com/
https://www.digizol.com/
https://www.digizol.com/2013/07/second-highest-frequency-characters.html
true
7440473
UTF-8
Loaded All Posts Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH ALL POSTS Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow THIS CONTENT IS PREMIUM Please share to unlock Copy All Code Select All Code All codes were copied to your clipboard Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy