Find the number of Strings


  • 1
    V

    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


  • 0

    Was this on site or phone interview? Thanks


  • 5
    A

    Following recursive solution without memoization would be good. For every index we have 3 option. According to valid condition we can put the desired character. Call the function as solve(0,0,0);

    int n;
    int dp[n][2][3]; // initially fill dp with -1
    int solve(int i, int bused, int c){
         if(i>=n) return 1;
         if(dp[i][bused][c]!=-1)
               return dp[i][bused][c];
         int ans=0;
         if(bused==0)
            ans+=solve(i+1,1,0);   // putting b
        ans += solve(i+1,bused, 0); // putting a
       if(c<2)
          ans+=solve(i+1, bused, c+1);
       return dp[i][bused][c]=ans;
    }
    

  • 0
    V

    I would really appreciate if somebody can post detailed thought process to solve these kind of problems ( generate strings subjected to many constraints).


  • 0

    @vijayks I will try till the end of the next week to publish my solution, because at the moment I am busy. My solution was also based on memoization and DP, but only in 2D space, not 3D, but I took pairs of letters, aa,ac,cc,ca, in case there is no b in the string. Actually if you think a little bit over the problem you can split the porblem in multiple cases and you will find the formule.


  • 5
    J

    Actually, it's just a counting problem if you notice that the number of strings that don't contain "b" is a Tribonacci number.

    The only complicated thing about this is to note that the number of strings that don't contain "b" is given by the following recurrence: x_n = x_{n-1} + x_{n-2} + x_{n-3}

    Let x_n be the number of different strings of length n that can made without using any "b" letter.

    These strings can start with:

    • axx...xxx and then the number of different strings is x_{n-1}
    • caxx..xxx and then the number of different strings is x_{n-2}
    • ccaxx...xxx and then the number of different string is x_{n-3}

    Our base cases are easy to compute:

    • x_1 = 2
    • x_2 = 4
    • x_3 = 7.

    This sequence is also known as Tribonacci number.

    def number_of_strings(n):
        tribo = [1, 2, 4]
    
        a, b, c = tribo
        for _ in xrange(n - 2):
            a, b, c = b, c, a + b + c
            tribo.append(c)
    
        return sum([tribo[i] * tribo[n - i - 1] for i in range(n)]) + tribo[n]
    
    assert number_of_strings(1) == 3
    assert number_of_strings(2) == 8
    assert number_of_strings(3) == 19
    assert number_of_strings(4) == 43
    assert number_of_strings(5) == 94
    assert number_of_strings(6) == 200
    assert number_of_strings(7) == 418
    assert number_of_strings(8) == 861
    

    Edit: I fixed the code after @pbarrera told me that there was a mistake. I also added more test cases.


  • 0
    V

    @elmirap
    Sure. Thanks


  • 0
    Z
    This post is deleted!

  • 0
    A

    @juruen
    cool, can you provide a simpler explanation, I couldn't understand the relation that well. Thank you.


  • 1
    C

    @Ab4188 It's a counting problem. I count it differently. Here is how. There are 6 cases to consider: {0,1} b's and {0,1,2} c's.

    Case I: (0,0) => n a
    Case II: (0,1) => n-1 a and 1 c
    Case III: (0,2) => n-2 a and 2 consecutive c
    Case IV: (1,0) => n-1 a and 1 b
    Case V: (1,1) => n-2 a and 1 b and 1 c
    Case VI: (1,2) => n-3 a and 1 b and 2 consecutive c

    Note that strings generated in the above manner are all unique (because you have either different number of a, or b, or c.)

    Summing all 6 cases you will get:
    1 + n + (n-1) + n + n(n-1) + (n-1)(n-2) = 2n^2 - n + 2.

    n = 3 => 9 + 6 + 1 = 17
    Note that in your examples, cac and cbc should not be counted, because they are not consecutive c's.

    Note2 if the condition of 2 consecutive c is relaxed to 2 c's. I get the same answer. n=3 => 19.


  • 0
    J

    @cau-seoi-dyun-dou

    Note that the problem statement clearly says:

    and can only have up to two consecutive 'c's

    If that's not clear enough for you, have a look at the provided example, and you will see that what you state here:

    Note that in your examples, cac and cbc should not be counted, because they are not consecutive c's.

    is not what is being asked. Those two examples should be totally counted. Actually, they show up in the example as valid strings :)

    Thanks.


  • 0
    C

    @juruen The wording is clear, but there is inconsistency. If you take the example as authority, then the wording consecutive should be removed. If you take the wording as authority, then two consecutive c's really mean consecutive. The case of one c is always consecutive.


  • 0
    J

    @cau-seoi-dyun-dou We might be interpreting the statement differently.

    But for me it's clear that up to two consecutive 'c's means that you can use as many 'c's as you like as along as you don't have more than two consecutive 'c's. And consecutive in this case means that a 'c' is followed by another 'c'.

    I still don't see how you can interpret it otherwise :/


  • 0

    @juruen The problem states that you can have at most 2 consecutive "c". This means that you can have more than 2 letters "c" but they should not be consecutive .For example baaaccca is invalid, but caaccaaab is valid string. Hope this helps


  • 0
    J

    @elmirap Yeah, that is also my interpretation and how I solved it.

    Thanks!


  • 0

    @juruen welcome


  • 0

    I think there is an mistake in @juruen orignal code. The approximation using Tribonacci numbers is interesting but you need to considere two sequences.

    E(n) = E(n-1) + E(n-2) + E(n-3) + E'(n-1) + E'(n-2) + E'(n-3)
    

    Where E(n) is the number all the sequences with n characters and E'(n) is the number of all sequences with n characters without any b.

    You can reach this splitting E(n) in three parts: sequences starting with A, with B and C: E(n) = A(n) + B(n) + C(n). It's clear that A(n) = E(n-1). B(n) = E'(n-1). But C(n) is more tricky. You need to consider sequences not starting with ccc, so C(n) = A(n-1) + A(n-2) + B(n-1) + B(n-2).

    Using the same approach in E'(n) and combining all terms you can reach a compact solution:

    E(n) = E(n-1) + E(n-2) + E(n-3) + E'(n-1) + E'(n-2) + E'(n-3)
    

    In code:

    def solution(n):
        if n <= 0:
            return 0
        if n == 1:
            return 3
        if n == 2:
            return 8
        E, E1, E2, E3, Ep, Ep1, Ep2, Ep3 = 19, 8, 3, 0, 7, 4, 2, 0
        for _ in range(3, n):
            Ep1, Ep2, Ep3 = Ep, Ep1, Ep2
            E1, E2, E3 = E, E1, E2
            Ep = Ep1 + Ep2 + Ep3
            E = E1 + E2 + E3 + Ep1 + Ep2 + Ep3
        return E
    

    I can be later simplified to @juruen's current solution (that works fine), but I find this one simpler to understand.


  • 0

    @pbarrera problem dublicates with this one :https://discuss.leetcode.com/topic/55326/count-strings


  • 0

    @elmirap Thanks, linking the two problems.


  • 0
    L

    @ankurverma1994
    Nice solution! Formatting it better -

    int n;
    int dp[n][2][3]; // initially fill dp with -1
    int solve(int i, int bused, int c) {
        if (i >= n)
            return 1;
        if (dp[i][bused][c] != -1)
            return dp[i][bused][c];
        int ans = 0;
        if (bused == 0) {
            ans += solve(i + 1, 1, 0); // putting b
        }
        ans += solve(i + 1, bused, 0); // putting a
        if (c < 2) { // putting c only if the current one does not end with 2 consecutive c's
            ans += solve(i + 1, bused, c + 1); 
        }
        return dp[i][bused][c] = ans;
    }
    

Log in to reply
 

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