(UVA) String Popping - Solution

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

Every time that a group of at least two same characters is found, these characters are erased, and a new string containing the remaining characters is created. This process happens until it finds out whether the string can be empty or not. Therefore, it was used backtracking.


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

class Main {
    public static boolean canBeEmpty;
   
    public static void rec(String s) {
        if (s.equals("")) {
            canBeEmpty = true;
        }
        if (canBeEmpty) {
            return;
        }
       
        for (int i = 0; i < s.length(); i++) {
            int countEqual = 0;
            for (int j = i+1; j < s.length(); j++) {
                if (s.charAt(j) != s.charAt(i)) {
                    break;
                }
                countEqual++;
            }
            if (countEqual == 0) {
                continue;
            }
            StringBuilder sb = new StringBuilder();
            sb.append(s.substring(0, i));
            sb.append(s.substring(i+countEqual+1, s.length()));
            rec(sb.toString());
            i += countEqual;
        }
    }
   
    public static void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
       
        int numTests = sc.nextInt();
        for (int i = 0; i < numTests; i++) {
            String s = sc.next();
            canBeEmpty = false;
            rec(s);
           
            if (canBeEmpty) {
                System.out.println("1");
            }
            else {
                System.out.println("0");
            }
        }
                                       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

Comments

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução