Java Heap space error while checking very very long String

Question

I have a specified String and I need to check this String for identical parts of specified length. For example if the String is "abcdab" and the length is specified as 2, the identical parts in this string are "ab" (always looking for the most repeated one). I reworked my algorithm 4-5 times for the best performance, but in the end, if the length of the String is 1m+, it throws an Java Heap space error.

So my question is: how to solve the error, maybe there is another way of checking the identical parts, or maybe some other way how to construct the whole algorithm. I figured out 1 possible solution of this, but it works very slowly, so I'm asking only for solutions as fast as my current algorithm or perhaps, even faster ones. Here is the current code:

int length = 2;
String str = "ababkjdklfhcjacajca";
ArrayList<String> h = new ArrayList<String>(); 
h.add(str.substring(0, length));
ArrayList<Integer> contains = new ArrayList<Integer>();
contains.add(1);

String c;
for (int g = 1; g < str.length()-length+1; g++) {
    c = str.substring(g, length+g);
    for (int e = 0; e < h.size(); e++) {
        if (h.get(e).charAt(0) == c.charAt(0) && h.get(e).charAt(length-1) == c.charAt(length-1)) {
            if (h.get(e).equals(c)) {
                contains.set(e, contains.get(e)+1);
                break;
            }
        }
        else if (e+1 == h.size()) {
            h.add(c);
            contains.add(1);
            break;
        }
    }

}

ArrayList h stores every unique part of the String, ArrayList contains represents amount of repeats of that every unique part of the string. String c is the main problem (java heap space points here). It gradually represents each part of the string before it gets stored in the ArrayList h (if that c is unique). After that I'll just find the most repeated ones by using the ArrayLists and print them.

Answer 1

If you want to do the search efficiently, time and memory wise, I suggest you the following:

1. First, create a simple character histogram containing the number of occurrences of each character. If a substring’s first character has less occurrences than the most common substring we’ve found so far, we can skip this substring.

2. Instead of creating substrings which contain copies of the character contents, we use a CharBuffer which wraps the string and adjust its position and limit to represent a subsequence. Of course, we must not modify a buffer once it has been stored as key in our map, so we create a new buffer for each key when it has been stored in the map. So we create at most one CharBuffer for each distinct substring and these buffers still only wrap the String rather then copy any character data

public static Map<String,Integer> mostCommonSubstring(String s, int len) {
    int[] charHistogram = new int[Character.MAX_VALUE+1];
    s.chars().forEach(ch -> charHistogram[ch]++);
    int most = 0;
    HashMap<Buffer, Integer> subStrings = new HashMap<>();
    CharBuffer cb = CharBuffer.wrap(s);
    for(int ix = 0, e = s.length()-len; ix <= e; ix++) {
        if(charHistogram[s.charAt(ix)] < most) continue;
        int num = subStrings.merge(cb.limit(ix+len).position(ix), 1, Integer::sum);
        if(num == 1) cb = CharBuffer.wrap(s);
        if(num > most) most = num;
    }
    final int mostOccurences = most;
    return subStrings.entrySet().stream()
        .filter(e -> e.getValue() == mostOccurences)
        .collect(Collectors.toMap(e -> e.getKey().toString(), Map.Entry::getValue));
}

The first two lines create our histogram

    int[] charHistogram = new int[Character.MAX_VALUE+1];
    s.chars().forEach(ch -> charHistogram[ch]++);

Within the loop

        if(charHistogram[s.charAt(ix)] < most) continue;

checks whether the first character of the current substring has less occurrences than the most common string we’ve found so far and skip the subsequent test in that case.

The next line adapts the current buffer to represent the substring, and updates the map, associating the buffer with 1 if not present or add 1 to the count of the existing mapping.

        int num = subStrings.merge(cb.limit(ix+len).position(ix), 1, Integer::sum);

We use the returned value to detect whether the merge operation has created a new association in the map, which is only the case if the result is one. In that case, we must not modify the buffer afterwards, hence, create a new one

        if(num == 1) cb = CharBuffer.wrap(s);

Then, we use the result to keep track of the highest number of occurrences

        if(num > most) most = num;

The final step after the loop is simple. We already have the highest number of occurrences, filter the map to keep entries with a matching number (there might be a tie) and create a new map, now converting the buffers to String instances as we don’t want to keep references to the original String and it affects only the few result substrings anyway.

    final int mostOccurences = most; // needed because most is not “effectively final”
    return subStrings.entrySet().stream()
        .filter(e -> e.getValue() == mostOccurences)
        .collect(Collectors.toMap(e -> e.getKey().toString(), Map.Entry::getValue));

Answer 2

you could try using a Map to track the occurrences of substrings, for example:

public class Test {
    public static void main(String[] args) {
        String test = "asdasdagagsjug8afhnqh3gbq29873brfuysbf78sdgy0yg7483wthsddbfahbfasfga78dftg78VGFIBDVGIUASF8928HWEAWD";
        int substringLength = 2;

        Map<String, Integer> tracker = new HashMap<>();

        for(int i = 0; i < test.length() - substringLength + 1; i ++) {
            String subString = test.substring(i, substringLength + i);
            tracker.compute(subString, (k,v) -> v == null ? 1 : v + 1);
        }

        for(String key : tracker.keySet()) {
            System.out.println("Substring: " + key + " has " + tracker.get(key) + " occurences.");
        }
    }
}

In your example you are tracking every occurrence separately. For example, in a String:

ababababababababababababa

you would store each substring separately in your List h. The above code would track the String ab in 1 mapping instead. In fact, it'd print:

Substring: ab has 12 occurences.
Substring: ba has 12 occurences.

I hope that gives you a place to start with.

Answer 3

You could iterate through the string one time by adding the location g to g+1 to a hash table, and then use an if to check if the occurence is in the hashtable. For example, abcab would be ab ->2, bc->1, ca->1 in the table.

int length = 2;
String str = "ababkjdklfhcjacajca";
Hashtable<String, Integer> identicalStrings = new Hashtable<String, Integer>();
h.add(str.substring(0, length));

for (int i = 0; i < str.length() - 1; i++) {
   if(!identicalStrings.contains(str.substring(i, i+2)) {
        identicalStrings.numbers.put(str.substring(i, i+2), 1);
   } else {
       identicalStrings.put(str.substring(i, i+2), identicalStrings.get(str.substring(i, i+2)) + 1);
   }

}

I wrote this out real quick so I am not sure if it compiles, but something similar to this should work.

Answer 4

It's a fun study case for using a Map (to represent the number of occurrences for each substring), Pattern and Matcher classes.

Another thing that was also interesting for me was that a substring aa - for example - appears 2 times in aaa; and not 1 time as I initially counted, using replaceAll method (for counting single characters).


My solution
(I've tested it with a 10^8=100,000,000 characters long String and it worked well. The only boundary that seems to exist is the length of the String input)

public static Map<String, Integer> getMostRepeatedSubstring(int length, String str) {
    HashSet<String> possibleSubstrings = new HashSet<>();
    Map<String, Integer> ans = new HashMap<>();
    int max = 0;

    // Create a list of all the unique substrings of "str" with a certain length
    for(int i=0; i<str.length()-length; i++) {
        String curr = str.substring(i, i+length);
        possibleSubstrings.add(curr);
        // "curr" is added only if it doesn't already appear within "possibleSubstrings"
    }

    for(String sub : possibleSubstrings) {
        Pattern pattern = Pattern.compile(sub, Pattern.LITERAL);
        Matcher matcher = pattern.matcher(str);
        int currentOccurrences = 0;
        while (matcher.find())
            currentOccurrences ++;

        if(currentOccurrences > max) {           // We have a new winner!
            max = currentOccurrences;
            ans.clear();
            ans.put(sub, currentOccurrences);
        }
        else if (currentOccurrences == max) {    // We have a tide
            ans.put(sub, currentOccurrences);
        }
    }

    return ans;
}

Edit: Thank you @Holger for the important improvements!