Ilan Aizelman WS Ilan Aizelman WS -4 years ago 37
Java Question

Getting all the substrings as keys and their occurcences as values with hashmap

Problem: Given a string, I want to get all the substrings of

length = k
using
Hash Map
.

So I've declared a
public static function getHistogram
which returns
Map<String,Integer>
and I'm trying to use a HashMap to get all the sub strings (as keys) of that given string, and every sub string that already occured in the string, I want to increment the value in its key (will be the counter).

This is what I've got so far: Currenet output: outputs not as expected.

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Iterator;
import java.util.Set;

public class Main2{

public static void main(String[] args) throws InvalidValueException{
// Get a set of the entries
Set set = Main2.getHistogram("ababaca", 5).entrySet();

// Get an iterator
Iterator i = set.iterator();

// Display elements
while(i.hasNext()) {
Map.Entry me = (Map.Entry)i.next();
System.out.print(me.getKey() + ": ");
System.out.println(me.getValue());
}
System.out.println();
}

public static Map<String,Integer> getHistogram(String str, int k)
throws InvalidValueException
{
int i,j;
String tempStr;

Map<String, Integer> hmap = new HashMap<String, Integer>();
for(i = 0; i < str.length(); i++)
{
for(j=i; j < str.length(); j++){
tempStr = str.substring(i, j);
int count = hmap.containsKey(tempStr) ? hmap.get(tempStr) : 0;
hmap.put(tempStr, count + 1);
}

}
return hmap;
}
}


Edit: Has to use count + 1 instead of count++, but still not fixed entirely.

Output:

: 7
a: 3
ab: 2
aba: 2
b: 2
bab: 1
ac: 1
c: 1
bac: 1
abac: 1
abab: 1
baba: 1
babac: 1
ababa: 1
ababac: 1
ba: 2

Answer Source
public class Substr {
    public static void main(String[] args) {
        System.out.println(getHistogram("ababaca", 5));
        System.out.println(getHistogram("ababaca", 4));
        System.out.println(getHistogram("ababaca", 3));
        System.out.println(getHistogram("ababaca", 2));
        System.out.println(getHistogram("ababaca", 1));
    }

    public static Map<String, Integer> getHistogram(String str, int k) {
        Map<String, Integer> hmap = new HashMap<>();
        for (int start = 0; start < str.length() - k + 1; start++) {
            String substring = str.substring(start, start + k);
            int count = hmap.containsKey(substring) ? hmap.get(substring) : 0;
            hmap.put(substring, count + 1);
        }
        return hmap;
    }    
}

This seems to yield the correct results.

If k is fixed, you don't need two loops, just one. It just runs through the beginning indices of possible substrings. Then we take the substring and count the number of substrings as you initially suggested.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download