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

i had coding interview on phone , asked question:

given string (for example):

"aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc"

and expression (for example):

"a+b+c-"

where:

+: means char before repeated 2 times

-: means char before repeated 4 times

find number of times given expression appears in string operands occurring non continuously , 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 it. started doing iterative brute force method lots of marking of indices realized how messy , hard 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 arraylist of chars iterate through expression , match string         for(int = 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 '-'                 exp.append(curr).append(curr).append(curr).append(curr);                 list.add(exp.tostring().tochararray());             }         }          char[] inputarray = input.tochararray();         int = 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                       * possible combinations in array list                      * 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 lot of time doing iteratively mentioned recursion , still couldn't see clear way doing recursively , wasn't able solve question. trying solve post-interview , still not sure how go question. how should go solving problem? solution obvious? thought hard question coding phone interview.

non-recursion algorithm requires o(m) space , operates in o(n*m), m number of tokens in query:

@test public void subequences() {      string input = "aabbccaacccccbbd";     string query = "a+b+";      // here store tokens of query: e.g. {a, +}, {b, +}     char[][] q = new char[query.length() / 2][];      // here store counts of subsequences ending j-th token found far     int[] c =  new int[query.length() / 2];   // main     int[] cc = new int[query.length() / 2];   // aux              // tokenize     (int = 0; < query.length(); += 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     (int = 0; < input.length(); i++) {          shift(sub2, input.charat(i));         shift(sub4, input.charat(i));          boolean all2 = sub2[1] != 0 && sub2[0] == sub2[1];  // true if sub2 chars same         boolean all4 = sub4[3] != 0 && sub4[0] == sub4[1]   // true if sub4 chars same               && sub4[0] == sub4[2] && sub4[0] == sub4[3];          // iterate tokens         (int j = 0; j < c.length; j++) {              if (all2 && q[j][1] == '+' && q[j][0] == sub2[0]) // found match "+" token                 cc[j] = j == 0             // filling aux array                       ? c[j] + 1           // first token, increment counter 1                       : c[j] + c[j - 1];   // add value of preceding token counter              if (all4 && q[j][1] == '-' && q[j][0] == sub4[0]) // found match "-" token                 cc[j] = j == 0                        ? c[j] + 1                        : c[j] + c[j - 1];         }         if (all2) sub2[1] = 0;  // clear, make "aa" occur in "aaaa" 2, not 3 times         if (all4) sub4[3] = 0;         copy(cc, c);            // copy aux array main          }     }     system.out.println(c[c.length - 1]); }   // shifts array 1 char left , puts c @ end void shift(char[] cc, char c) {     (int = 1; < cc.length; i++)         cc[i - 1] = cc[i];     cc[cc.length - 1] = c; }  // copies array contents  void copy(int[] from, int[] to) {     (int = 0; < from.length; i++)         to[i] = from[i]; } 

the main idea catch chars input 1 one, holding them in 2- , 4-char accumulators , check if of them match tokens of query, remembering how many matches have got sub-queries ending these tokens far.

query (a+b+c-) splitted tokens (a+, b+, c-). collect chars in accumulators , check if match tokens. if find match first token, increment counter 1. if find match j-th token, can create many additional subsequences matching subquery composed of tokens [0...j], many of them exist for subquery composed of tokens [0... j-1], because match can appended every of them.

for example, have:

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

when cccc arrives. c- counter should increased b+ counter value, because far have 2 a+b+ subsequences , cccc can appended both of them.