Finding the Number of Times an Expression Occurs in a String Continuously and Non Continuously

Question

I had a coding interview over the phone and was asked this question:

Given a String (for example):

"aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc"

and an expression (for example):

"a+b+c-"

where:

+: means the char before it is repeated 2 times

-: means the char before it is repeated 4 times

Find the number of times the given expression appears in the string with the operands occurring non continuously and continuously.

The above expression occurs 4 times:

1) aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc
        ^^       ^^       ^^^^                    
        aa       bb       cccc
2) aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc
        ^^       ^^                               ^^^^
        aa       bb                               cccc

3) aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc
        ^^                                ^^      ^^^^
        aa                                bb      cccc

4) aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc
                                       ^^ ^^      ^^^^
                                       aa bb      cccc

I had no idea how to do it. I started doing an iterative brute force method with lots of marking of indices but realized how messy and hard that would to code half way through:

import java.util.*;

public class Main {

    public static int count(String expression, String input) {
        int count = 0;
        ArrayList<char[]> list = new ArrayList<char[]>();

        // Create an ArrayList of chars to iterate through the expression and match to string
        for(int i = 1; i<expression.length(); i=i+2) {
            StringBuilder exp = new StringBuilder();
            char curr = expression.charAt(i-1);
            if(expression.charAt(i) == '+') {
                exp.append(curr).append(curr);
                list.add(exp.toString().toCharArray());
            }
            else { // character is '-'
                exp.append(curr).append(curr).append(curr).append(curr);
                list.add(exp.toString().toCharArray());
            }
        }

        char[] inputArray = input.toCharArray();
        int i = 0; // outside pointer
        int j = 0; // inside pointer
        while(i <= inputArray.length) {
            while(j <= inputArray.length) {
                for(int k = 0; k< list.size(); k++) {
                    /* loop through 
                     * all possible combinations in array list
                     * with multiple loops
                     */
                }
                j++;
            }
            i++;
            j=i;
        }
        return count;
    }

    public static void main(String[] args) {
        String expression = "a+b+c-";
        String input = "aaksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc";
        System.out.println("The expression occurs: "+count(expression, input)+" times");
    }
}

After spending a lot of time doing it iteratively he mentioned recursion and I still couldn't see a clear way doing it recursively and I wasn't able to solve the question. I am trying to solve it now post-interview and am still not sure how to go about this question. How should I go about solving this problem? Is the solution obvious? I thought this was a really hard question for a coding phone interview.

Answer 1

Non-recursion algorithm that requires O(m) space and operates in O(n*m), where m is number of tokens in query:

@Test
public void subequences() {

    String input = "aabbccaacccccbbd";
    String query = "a+b+";

    // here to store tokens of a query: e.g. {a, +}, {b, +}
    char[][] q = new char[query.length() / 2][];

    // here to store counts of subsequences ending by j-th token found so far
    int[] c =  new int[query.length() / 2];   // main
    int[] cc = new int[query.length() / 2];   // aux        

    // tokenize
    for (int i = 0; i < query.length(); i += 2)
        q[i / 2] = new char[] {query.charAt(i), query.charAt(i + 1)};

    // init
    char[] sub2 = {0, 0};        // accumulator capturing last 2 chars
    char[] sub4 = {0, 0, 0, 0};  // accumulator capturing last 4 chars

    // main loop
    for (int i = 0; i < input.length(); i++) {

        shift(sub2, input.charAt(i));
        shift(sub4, input.charAt(i));

        boolean all2 = sub2[1] != 0 && sub2[0] == sub2[1];  // true if all sub2 chars are same
        boolean all4 = sub4[3] != 0 && sub4[0] == sub4[1]   // true if all sub4 chars are same
              && sub4[0] == sub4[2] && sub4[0] == sub4[3];

        // iterate tokens
        for (int j = 0; j < c.length; j++) {

            if (all2 && q[j][1] == '+' && q[j][0] == sub2[0]) // found match for "+" token
                cc[j] = j == 0             // filling up aux array
                      ? c[j] + 1           // first token, increment counter by 1
                      : c[j] + c[j - 1];   // add value of preceding token counter

            if (all4 && q[j][1] == '-' && q[j][0] == sub4[0]) // found match for "-" token
                cc[j] = j == 0 
                      ? c[j] + 1 
                      : c[j] + c[j - 1];
        }
        if (all2) sub2[1] = 0;  // clear, to make "aa" occur in "aaaa" 2, not 3 times
        if (all4) sub4[3] = 0;
        copy(cc, c);            // copy aux array to main 
        }
    }
    System.out.println(c[c.length - 1]);
}


// shifts array 1 char left and puts c at the end
void shift(char[] cc, char c) {
    for (int i = 1; i < cc.length; i++)
        cc[i - 1] = cc[i];
    cc[cc.length - 1] = c;
}

// copies array contents 
void copy(int[] from, int[] to) {
    for (int i = 0; i < from.length; i++)
        to[i] = from[i];
}

The main idea is to catch chars from the input one by one, holding them in 2- and 4-char accumulators and check if any of them match some tokens of the query, remembering how many matches have we got for sub-queries ending by these tokens so far.

Query (a+b+c-) is splitted into tokens (a+, b+, c-). Then we collect chars in accumulators and check if they match some tokens. If we find match for first token, we increment its counter by 1. If we find match for another j-th token, we can create as many additional subsequences matching subquery composed of tokens [0...j], as many of them now exist for subquery composed of tokens [0... j-1], because this match can be appended to every of them.

For example, we have:

a+ : 3  (3 matches for a+)
b+ : 2  (2 matches for a+b+)
c- : 1  (1 match for a+b+c-) 

when cccc arrives. Then c- counter should be increased by b+ counter value, because so far we have 2 a+b+ subsequences and cccc can be appended to both of them.