(UVA) The Ouroboros Problem - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1447

The solution below try all the possible combinations. However, in order to reduce the execution time, every time we add a digit to our string, we do a "pre-check" to discover if the combinations of numbers in the string is valid. This procedure is done only after we have a string with at least N characters.


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

class Main {
    public int amountDigits;
    public int base;
    public int totalLength;
    public ArrayList<Integer> list;
    public ArrayList<Integer> answer;
    public HashMap<Integer, Integer> count;
    public HashSet<String> strings;
    public HashSet<String> stringsFinal;
    public boolean gotAnswer;
    
    public boolean check() {
        stringsFinal = new HashSet<>();
        
        for (int i = 0; i < list.size()-amountDigits; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = i; j < i+amountDigits; j++) {
                sb.append(list.get(j));
            }
            stringsFinal.add(sb.toString());
        }   
        for (int i = 0; i < amountDigits; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = list.size()-amountDigits+i; j < list.size(); j++) {
                sb.append(list.get(j));
            }
            for (int j = 0; j < amountDigits || sb.length() == amountDigits; j++) {
                sb.append(list.get(j));
            }
            stringsFinal.add(sb.toString());
        }
        
        if (stringsFinal.size() == totalLength) {
            return true;
        }
        return false;
    }
    
    public String preCheck(int index) {
        StringBuilder sb = new StringBuilder();
        for (int i = index; i < list.size(); i++) {
            sb.append(list.get(i));
        }
        
        // in the end, it must have base^amountDigits strings
        if (strings.add(sb.toString())) { // if it does not have any string repeated
            return sb.toString();
        }
        return null;
    }
    
    public void rec(int position) {
        if (gotAnswer) {
            return;
        }
        if (position == totalLength) {
            if (!check()) {
                return;
            }
            answer = (ArrayList<Integer>) list.clone();
            gotAnswer = true;
            return;
        }
        
        for (int i = 0; i < base; i++) {
            // it cannot have more than totalLength/base same digit
            if (count.get(i) >= totalLength/base) {
                continue;
            }
            count.put(i, count.get(i)+1);
            list.add(i); // sequence
            String preCheckResult = null;
            if (list.size() >= amountDigits) {
                // 00001 -> (1)->(4): 0001
                preCheckResult = preCheck(list.size()-amountDigits);
                if (preCheckResult == null) {
                    list.remove(list.size()-1); 
                    count.put(i, count.get(i)-1);
                    continue;
                }
            }
            rec(position+1);
            if (list.size() >= amountDigits) {
                strings.remove(preCheckResult);
            }
            list.remove(list.size()-1); 
            count.put(i, count.get(i)-1);
        }
    }
    
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        
        while (sc.hasNext()) {
            amountDigits = sc.nextInt();
            base = sc.nextInt();
            
            totalLength = (int)Math.pow(base, amountDigits);
            
            count = new HashMap<>();
            for (int i = 0; i < base; i++) {
                count.put(i, 0);
            }
            strings = new HashSet<>();
            answer = new ArrayList<>();
            list = new ArrayList<>();
            gotAnswer = false;
            rec(0);
            
            for (int i = 0; i < answer.size()-1; i++) {
                System.out.print(answer.get(i));
            }
            System.out.println(answer.get(answer.size()-1));
        }
                       
        return;
    }
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
        
        System.exit(0);
    }
}