Calculate the frequency of characters in a string (Java, Performance)

Question

Problem

I wrote this program to check the number of times that each letter appears in a string input by the user. It works fine, but is there a more efficient or alternative solutions of going about this task than reiterating through a twenty-six-element-long array for every single character?

Code

import java.util.Scanner;
public class Letters {
    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner sc = new Scanner(System.in);
        char[] c = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
        int[] f = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        System.out.println("Enter a string.");
        String k = sc.nextLine();
        String s = k.toUpperCase();
        s = s.trim();
        int l = s.length();
        System.out.println("Checking string = " + s);
        char ch;
        for (int i = 0; i < l; i++) {
            ch = s.charAt(i);
            for (int j = 0; j < c.length; j++) {
                if (ch == c[j]) {
                    f[j]++;
                }
            }
        }
        System.out.println("Char\tFreq");
        for (int i = 0; i < c.length; i++) {
            if (f[i] != 0) {
                System.out.println(c[i] + "\t" + f[i]);
            }
        }
    }
}

I believe this question is more suitable for -> https://codereview.stackexchange.com/ — vs97, Mar 17 '19 at 03:30
One simple way is to use the Stream API. See [here](https://stackoverflow.com/questions/25441088/group-by-counting-in-java-8-stream-api). — MikaelF, Mar 17 '19 at 03:32
You could use `f[ch - 'A']++` to avoid the inefficient iteration. — dave, Mar 17 '19 at 03:41

score 1 · Accepted Answer · answered Mar 17 '19 at 03:45

1

You don't need to explicitly initialize 26 entries in your frequency array (the default value is zero); you also don't need to keep the table of characters (it is sufficient to know the offset). That is, your code can eliminate c entirely and calculate each letter; like,

Scanner sc = new Scanner(System.in);
int[] f = new int[26];
System.out.println("Enter a string.");
String orig = sc.nextLine();
String k = orig.trim().toUpperCase();
System.out.println("Checking string = " + orig);
for (char ch : k.toCharArray()) {
    f[ch - 'A']++;
}
System.out.println("Char\tFreq");
for (int i = 0; i < f.length; i++) {
    if (f[i] != 0) {
        System.out.println((char) ('A' + i) + "\t" + f[i]);
    }
}

answered Mar 17 '19 at 03:45

Elliott Frisch

198,278
20
158
249

In the line for (char ch : k.toCharArray()) I've never seen a for loop's definition with that sort of construction (mine has always been initialization, condition and increment), so could you please clarify that for me? – Ronit Danti Mar 17 '19 at 04:02
@ArtemisHunter [`for-each`](https://stackoverflow.com/questions/85190/how-does-the-java-for-each-loop-work) `char ch` in the `char[]` returned from the `String k` by [`toCharArray()`](https://docs.oracle.com/javase/8/docs/api/java/lang/String.html#toCharArray--)... – Elliott Frisch Mar 17 '19 at 19:10
@ElliottFrisch That clarifies it. Thanks! – Ronit Danti Mar 18 '19 at 01:49

FailingCoder · Answer 2 · 2019-11-09T23:42:19.463

1

You can find the frequency of characters in a String by writing

String.length() - String.replace("character", "").length();

edited Nov 09 '19 at 23:42

answered Mar 17 '19 at 04:18

FailingCoder

757
1
8
20

score 0 · Answer 3 · answered Mar 17 '19 at 03:56

0

You avoid the inner loop by using the fact that letters A-Z appear consecutively in ASCII. So, you don't have to search for the character in the array c, just compute the index. See code below:

for (int i = 0; i < l; i++) {
    char ch = s.charAt(i);
    if (ch >= 'A' && ch <= 'Z') {
        int j = (int)(ch - 'A'); // j will be in the range [0, 26)
        f[j]++;
    } 
}

We can get rid of the array c also similarly.

for (int i = 0; i < 26; i++) {
    if (f[i] != 0) {
        System.out.println((char)('A' + i) + "\t" + f[i]);
    }
}

answered Mar 17 '19 at 03:56

Manu

76
1
4

So, it's essentially confirming that the character is a letter and then using its ASCII code to refer to the corresponding index? I'm still a little confused as to (ch - 'A')'s working. – Ronit Danti Mar 17 '19 at 04:03
Yes, that is the idea. (ch-'A') basically takes the ASCII (Actually UTF16, but for english letters they are the same) and subtract the ASCII of 'A' giving you the index. Btw, @ElliottFrisch's code above doesn't check that the char is A-Z, so if there is a non-letter character in the input, it will throw ArrayIndexOutOfBoundsException – Manu Mar 18 '19 at 03:59

score 0 · Answer 4 · answered Mar 17 '19 at 04:19

0

If we have strings like "romeo@alphacharlie.com", then the example having freqArr[c - 'A']++ will not work. You can try using this.

private static int[] decodeFrequency(char[] array) {
    int[] freqArr = new int[127];
    for ( char c : array ) {
        freqArr[(int)c]++;
    }
    return freqArr;
}

answered Mar 17 '19 at 04:19

The Roy

2,178
1
17
33

Thanks a lot for pointing that out. I haven't understood why there's a necessity for the array to have a length of 127 though (aren't there only 26 letters in the alphabet?). It would be great if you could explain that. – Ronit Danti Mar 17 '19 at 04:22
I have used the entire ASCII table length. https://ee.hawaii.edu/~tep/EE160/Book/chap4/subsection2.1.1.1.html – The Roy Mar 17 '19 at 04:25

score 0 · Answer 5 · edited Jun 20 '20 at 09:12

There are many ways to solve the problem, I would encourage you to follow one which you understand easily. My solution below basically initializes an array of 26 to count the frequency of all the characters.

Important part :

Every alphabet will have a ASCII value so, by typecasting you eventually get the integer value and then by subtracting 65 (For Upper Case alphabets) you will get the index of the array to store the frequency of respective character.

Your Modified Java Code

import java.util.Scanner;
public class Letters{
    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner sc = new Scanner(System.in);
        int[] f = new int[26];
        System.out.println("Enter a string.");
        String k = sc.nextLine();
        String s = k.toUpperCase();
        s = s.trim();
        int l = s.length();
        System.out.println("Checking string = " + s);
        char ch;
        for (int i = 0; i < l; i++) {
            ch = s.charAt(i);

            //This will give the ASCII value of the character i.e. ch
            int temp=(int)ch;
            if(temp>=65 && temp<=90){
              //subtract 65 to get index 
              //add 1 to increase frequency 
              f[temp - 65]+=1;
            }
            
        }
        System.out.println("Char\tFreq");
        for (int i = 0; i < 26; i++) {
            if (f[i] != 0) {
                //Add 65 to get respective character
                System.out.println((char)(i+65) + "\t" + f[i]);
            }
        }
    }
}

Eg:

f[0] for 'A'

f[1] for 'B'

....

f[25] for 'Z'

(Remember index start from 0)

This way you can eliminate inner for loop and get frequency with single integer array.

Java uses UTF-16, not ASCII. (Your algorithm happens to be equally valid for the characters in question, though.) And, `'A'` is much preferred to 65, etc. — Tom Blodget, Mar 17 '19 at 16:14

Calculate the frequency of characters in a string (Java, Performance)

Problem

Code

5 Answers5

Important part :