Having trouble with for loops

Question

So, I need to write a program using loops that takes a string and counts what and how many letters appear in that string. (string "better butter" would print "b appears 2 times, e appears 3 times, ' '(space) appears 1 time, and so on). While I understand the idea and concept behind this assignment, actually pulling it off has been rough.

My nested for loop is where the problems are coming from, I assume. What I've written only loops once (i think) and just shows the first character and says there's only one of that character.

Edit: Preferably without using Map or arrays. I'm fine with using them if it's the only way, but they've not been covered in my class so I'm trying to avoid them. Every other similar question to this (that I've found) uses Map or array.

import java.util.Scanner;

class myString{
    String s;

    myString() {
        s = "";
    }
    void setMyString(String s) {
        this.s = s;
    }
    String getMyString() {
        return s;
    }
    String countChar(String s){
        s = s.toUpperCase();
        int cnt = 0;
        char c = s.charAt(cnt);
        for (int i = 0; i <= s.length(); i++)
            for (int j = 0; j <= s.length(); j++)  //problem child here
                c = s.charAt(cnt);
                cnt++;
                if (cnt == 1)
                    System.out.println(c+" appears "+cnt+" time in "+s);
                else
                    System.out.println(c+" appears "+cnt+" times in "+s);
                return "for";  //this is here to prevent complaint from the below end bracket.
    }
}

public class RepeatedCharacters {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s;

        System.out.println("Enter a sentence: ");
        s = in.nextLine();


        myString myS = new myString();
     //   System.out.println(myS.getMyString());
     //   System.out.println(myS.countChar());
        myS.countChar(s);
                }

}

Answer 1

First you will need to scan the entire string and store the counts of each characters. Later you can just print the counts.

Algorithm 1:

1. Use a HashMap to store the character as key and its count as value. (If you are new to Java, you might want to read up on HashMaps.)

2. Every time you read a character in your for loop, check if it present in the HashMap. If yes, then increment the count by 1. Else add a new characters to the map with count 1.

Printing: Just iterate on your HashMap and print out the character and their respective counts.

Issue with your code: You are trying to print the count as soon as you read a character. But the character might appear again later in the string. So you need to keep track of the characters you have already read.

Algorithm 2:

String countChar(String s){
    has_processed = []
    for i = 0 to n
        cnt = 0
        if s.charAt(i) has been processed
            continue;
        for j = i+1 to n
            if (s.charAt(i) == s.charAt(j))
                cnt++
                add s.charAt(i) to has_processed array
        print the count of s.charAt(i)
}

Answer 2

Use a frequency array to get an answer in linear time.

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        String s = "better butter";

        int freq[] = new int[26];

        int i;
        for (i = 0; i < s.length(); i++) {
            if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z')
                freq[s.charAt(i)-'a']++;
        }

        for (i = 0; i < freq.length; i++) {
            if (freq[i] == 0) continue;
            System.out.println((char)(i+'a') + " appears " + freq[i] + " times" );
        }
    }
}

Ideone Link

Note that this can be expanded to include uppercase letters, but for demonstrative purposes, only lowercase letters are handled in the above code.

EDIT: While the OP did ask if it was possible to do this without an array, I would recommend against such. That solution would have terrible time complexity and repeat character counts (unless an array is used to keep track of seen characters, which is counter to the aim). Thus, the above solution is the best way to do it in a reasonable amount of time (linear) with limited space consumption.

Answer 3

I would do the following. Create a HashMap which keeps track of which unique characters are in the string and the count for each character.

You only need to iterate over the string once, and put each character into the HashMap. if the characer is in the map, icrement the integer count in the map, else add 1 to the map for that character. Print out the map with toString() to get the result. The whole thing can be done in about 4 lines of code.

Answer 4

The only thing being done in your nested for loop with the following

c = s.charAt(cnt)

is setting the c char to the value of the first letter (i.e. index 0 of the string) over and over and over until you've looped through the string n^2 times. In other words, you're not incrementing your cnt counter within the for loops at all.

Answer 5

Here is my version of countChar(String s)

boolean countChar(String s) {
    if(s==null) return false;
    s = s.toUpperCase();
    //view[x] will means that the characted in position x has been just read
    boolean[] view = new boolean[s.length()];

    /*
    The main idea is:
    foreach character c = s.charAt(x) in the string s, I have a boolean value view[x] which say if I have already examinated c.
    If c has not been examinated yet, I search for other characters equals to c in the rest of the string.
    When I found other characters equals to c, I mark it as view and I increment count with count++.
    */
    for (int i = 0; i < s.length(); i++) {
        if (!view[i]) {
            char tmp = s.charAt(i);
            int count = 0;
            for (int j = i; j < s.length(); j++) {
                if (!view[j] && s.charAt(j) == tmp) {
                    count++;
                    view[j] = true;
                }
            }
            System.out.println("There were " + count + " " + tmp);
        }
    }
    return true;
}

It should work, excuse me for my English because I'm italian

Answer 6

Suggestion: try to use meaningful names for your variables; it will help you a lot in your career. Also class names should always start with a capital letter.

Although it is not the quickest solution in terms of performance, the most simple solution should be:

import java.util.HashMap;
import java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
int count = freq.containsKey(word) ? freq.get(word) : 0;
freq.put(word, count + 1);

Source: Most efficient way to increment a Map value in Java

Please next time use the search function before posting a new question.