Count strings


  • 0

    Given a length n, return the number of strings of length n that can be made up of the letters 'a', 'b', and 'c', where there can only be a maximum of 1 'b's and can only have up to two consecutive 'c's

    Example:

    findStrings(3) returns 19
    since the possible combinations are: aaa,aab,aac,aba,abc,aca,acb,baa,bac,bca,caa,cab,cac,cba,cbc,acc,bcc,cca,ccb
    and the invalid combinations are:
    abb,bab,bba,bbb,bbc,bcb,cbb,ccc


  • 3
    S

    No need to list all possibilities. Similar to painting fence:

        public int countStrings(int n){
            int noB = noMoreThanTwoC(n);
            int oneB = n*noMoreThanTwoC(n-1);
            return noB+oneB;
        }
    
        public int noMoreThanTwoC(int n){
            int noMoreThanTwoConsecutives = paintFenceNumWays(n,2); // strings with only 'a' and 'c' with no more than two consecutive same chars
            int allPossibilities = (int)Math.pow(2,n); // strings with only 'a' and 'c'
            int noMoreThanTwoC = allPossibilities - (allPossibilities-noMoreThanTwoConsecutives)/2;
            return noMoreThanTwoC; // no more than 2 consecutive 'c's
        }
    
    
    

  • 1
    E

    Re: Count strings

    One other solution.. just thinking to define several states that we can go.

    There are 7 states - a, c, cc, b(transition state), ba, bc, bcc.
    And there are rules we can define for moving the states.

    From 'a' we can go 'a', 'c', or 'b'.
    From 'c' we can go 'a', 'cc', or 'b'
    From 'cc' we can go 'a', or 'b'
    From 'b' we can go 'ba' or 'bc'
    From 'ba' we can go 'ba' or 'bc'
    From 'bc' we can go 'ba' or 'bcc'
    From 'bcc' we can go 'ba'

    The point here is just setting b as a transition state so once we get 'b', you cannot go back to the states for 'a', or 'c', but new state 'ba' or 'bc'. Also, I use 'c' and 'cc' so that 'cc' can only go to the 'a', so no way to make 'ccc'.

    Maybe you can make a smaller code than this but the idea is defining states to move. I didn't test my code for bigger input, so let me know if you find some bugs here.

    int countString(int n) {
       if (n <= 0) {
          return 0;
       }
    
       int a = 1;
       int c = 1;
       int cc = 0;
    
       int b = 1;
    
       int ba = 0;
       int bc = 0;
       int bcc = 0;
    
       while (--n > 0) {
          int _a = a + c + cc;
          int _c = a;
          int _cc = c;
          int _b = a + c + cc;
          int _ba = b + ba + bcc + bc;
          int _bc = b + ba;
          int _bcc = bc;
    
          a = _a;
          b = _b;
          c = _c;
          cc = _cc;
          ba = _ba;
          bc = _bc;
          bcc = _bcc;
       }
    
       return a + c + cc + b + ba + bc + bcc;
    }
    

  • 0

    @espuer very good solution. I tested my solution with the output from your. There is an overflow for values greater 100, because of int type
    Here is my implementation using DP approach. I put some comments for more clearance

    int countWithoutB(int n, int[] f) {   
         if  (f[n] == 0) {       
             if (n == 1) 
                 f[n] = 2;
             else if (n == 2) 
                // aa,ca,ac,cc
                 f[n] = 4;
             else {        
                 int res = 0;
                 int r = 1;
                 int l = 1;
                 int l1 = 1;
                 if( n > 3) 
                     //cca*
                     r = countWithoutB(n - 3, f);          
                 if( n > 2) 
                     //ca*
                    l = countWithoutB(n - 2, f);   
                 if( n > 1)  
                     //a*
                    l1 = countWithoutB(n - 1, f);
                 res += l + r + l1;
                 f[n] = res;
             }
         }
         return f[n];
     }
     
     int countString(int n){
         if (n <= 0) {
             return 0;
         }
         int[] f = new int[n + 1];   
         int sum = 0;
         for (int i = 0; i < n; i++) {
             int l = 1;
             int r = 1;
             if (i > 0)
                 l = countWithoutB(i,f);
             if (n - i - 1 > 0)
                 r = countWithoutB(n - i - 1,f);         
             sum += l * r;        
         }     
         return  sum + countWithoutB(n,f);    
     }

  • 0

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.