SPOJ - Alphacode - Exceeds Time Limit I'm trying to solve Alphacode on SPOJ.  The challenge is to count the ways to split a string of up to 5000 digits into a sequence of numbers, each ranging from 1 to 26.

It works fine for small numbers but exceeds the time limit for bigger numbers. I'm using the exhaustive recursive traversing.

Is there a way to make it optimal?

import java.util.HashSet;
import java.util.Scanner;

public class AlphaCode {

    static int n;
    static HashSet&lt;String&gt; set;

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

        while (sc.hasNext()) {
            String s = sc.nextLine();
            if (s.equals("0")) {
                break;
            }
            n = s.length();
            char[] c = new char[n];
            set = new HashSet&lt;String&gt;();
            count = 0;
            solve(s, 0, c);
            System.out.println(count);
        }
    }

    static int count = 0;

    private static int solve(String s, int i, char[] st) {
        if (n == i) {
            // System.out.println(st);
            if (set.contains(st.toString())) {
                return 0;
            }
            count++;
            return 0;
        }
        for (int j = 0; j &lt; 2 &amp;&amp; i + j &lt; n; ++j) {
            int x = Integer.parseInt(s.substring(i, i + j + 1) + "");
            if (x &lt;= 26) {
                // System.out.println(i + " " + j + " " + s.substring(i, i + j +
                // 1));
                st[i] = (char) (x + 'A' - 1);
                solve(s, i + j + 1, st);
            }
        }
        return 0;
    }

}
Useless code

Currently, your code has some useless parts to it:


You have a set, but you never add anything to it.  When you reach the end of the string, you check your set for it containing something, but it never does.  You can just remove that whole set and do count++ when you reach the end of the string.  The way you are parsing the input, there is no way you can ever reach the same output string more than once.
Your solve() function always returns 0.  And nobody even checks the return value.  So you should make your solve() function return void.


Incorrect answer

Currently, your program will return an incorrect answer if count ever increases past \$2^{31}\$.  The question warned about this, so you should make count be long instead.

Too slow

The problem with your program is that you are just computing the answer in the brute force way, by generating every possible output.  This problem requires a dynamic programming technique to solve faster.  In simple terms, you are solving the same subproblem repeatedly.  If you just remembered the answer for each subproblem you already solved, then things would run much faster.

Here is an example of how I would fix your program to run faster:

import java.util.Scanner;

public class AlphaCode {    
    static int n;
    static long [] solved;

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

        while (sc.hasNext()) {
            String s = sc.nextLine();
            if (s.equals("0")) {
                break;
            }
            n = s.length();
            solved = new long[n];
            for (int i=0; i&lt;n; i++) {
                solved[i] = -1;
            }
            long ret = solve(s, 0);
            System.out.println(ret);
        }
    }

    private static long solve(String s, int i)
    {
        long count = 0;

        if (i &gt;= n) {
            return 1;
        }

        if (solved[i] != -1) {
            return solved[i];
        }

        for (int j = 0; j &lt; 2 &amp;&amp; i + j &lt; n; ++j) {
            int x = Integer.parseInt(s.substring(i, i + j + 1));
            if (x &lt;= 26) {
                count += solve(s, i + j + 1);
            }
        }
        solved[i] = count;
        return count;
    }

}