java.lang.OutOfMemoryError: Java heap space to find all strings of length n

I want to generate all possible strings of length n with alphabets a,b, and c .. I am getting this error java.lang.OutOfMemoryError: Java heap space. my heap size is 512m . Can you suggst me alternatives for this ..

-------------Problems Reply------------

Counting Strings not containing substring "ABC" can be solved with dynamic programming.

First, lets name the number of all strings of length n as S(n). Note that S(n) is easy to compute. S(n) = pow(size_of_the_alphabet,n)

Let's name the number all strings containing "ABC" of length n as A(n) and let's name the number of all strings having first ocurrence of "ABC" on k-th position as A(n,k)

Now note that: A(n,k) = (S(k-1) - A(k-1)) * S(n - k - 3) (since k is the first position where "ABC" occurs, each of these strings has a substring without "ABC" before this position and any substring after the first "ABC").

Note that A(n) = sum A(n,k) for k in [0..n-3]

So now we can calculate A(n) computing each value of A(n) starting from 0.

Base case is simple, as A(n) = 0 for n = 0,1,2

A(3) = (S(0) - A(0))*S(0) = 1 (namely "ABC")


Once you have A(n) you can get the number you're looking for using the formula S(n) - A(n).

Pseudojava pseudocode:

public class Counter {

public int count(int aSize, int n) {
long[] a = new long[n+1]; // n + 1 elements since a[i] contains # of strings containing "ABC"
a[0] = 0;
a[1] = 0;
a[2] = 0;

for (int i = 3; i <= n; ++i){
long sum = 0;
for (int k = 0; k <= i-3; ++k) {
sum += (pow(aSize, k) - a[k]) * pow(aSize, i - k - 3);
a[i] = sum;
return a[n];


public static void main(String... args) {
int aSize = 3; //size of the alphabet
int n = 30; // length of the strings

//final result
long result = pow(aSize, n) - count(aSize, n);


Running time is O(n^2), assuming pow is O(1). If it's not then you can save some time precalculating S(i).

Space requirement is O(n).

Note that this computes number of all strings with length == n. If you want length <= n then the modification is obvious (you just sum all elements in a).

The number of strings you are currently computing is

3^30 = 205 891 132 094 649

Which is quite a lot...

Knowing that each String contains three bytes:

3^30 * 3 = 617 673 396 283 947

Plus the 32-bit or 64-bit pointers of the two dimensional array.

3^30 * (3 + 4) = 1 441 237 924 662 540 // 32-bit Java VM
3^30 * (3 + 8) = 2 264 802 453 041 140 // 64-bit Java VM

Which is

2 109 261 GB = 2059 TB // 64-bit JVM

I guess that is the problem.

With your limit of 500 MB you can solve this equation:

3^x * (3 + 8) = 524 288 000
3^x = 47662545
x = log(47662545) / log(3)
x = 7 / 0.477121254719662
x = 14.67

So, if I forgot nothing, your tests should work for n <= 14. Of course, it won't work until you delete this code:

List<String> result = new ArrayList<String>();
for (char[] permutation : table) {
result.add(new String(permutation));

This code duplicates all the data! Which means that you need twice the amount of memory. Try to print it immediately.

I noted in your comment you have a different question. You want to find all the strings of length 30 with a-z which don't contains a-c. This is the count of all the string of length 30 which are d-z. The count is (26-3)^30.

System.out.printf("%,d%n", BigInteger.valueOf(26-3).pow(30));



Instead of remembering every string, you can encode every possible String as a number. In your case you can use a long.

public static void main(String... args) {
String letters = "abc";
int len = 30;
long combinations = (long) Math.pow(letters.length(), len);
System.out.printf("There are %,d strings%n", combinations);
for (long i = 0; i < 10; i++)
System.out.println(fromLong(i, letters, len));
System.out.println("... some numbers skipped ...");
for (long i = combinations-10; i < combinations; i++)
System.out.println(fromLong(i, letters, len));

public static String fromLong(long n, String letters, int len) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < len; i++) {
sb.append(letters.charAt((int) (n % letters.length())));
n /= letters.length();
return sb.reverse().toString();


There are 205,891,132,094,649 strings
... some numbers skipped ...

This can print every possible String from 0 to 3^30-1. You don't need to store all the encoded values because you know all the possible values are in a continuous range.

Are you trying to compute the strings or count the strings?

EDIT: I see from the later comment that you know how many Strings you're talking about: If you are only counting, that's a standard permutation closed form: 26^n = 26 raised to the nth power (assuming that you're only using lower case alphabet from 'a' to 'z').

If you are truly trying to enumerate every string, I strongly recommend that you ensure that you do not retain a reference to each String. If you end up with a dangling reference to each of those Strings, you're going to run out of memory after about six characters.

Category:java Views:0 Time:2011-12-20

Related post

Copyright (C), All Rights Reserved.

processed in 0.160 (s). 11 q(s)