Number of ways to insert two pairs of parentheses into a string of N characters

I came across an interesting codding problem at https://www.geeksforgeeks.org/number-of-ways-to-insert-two-pairs-of-parentheses-into-a-string-of-n-characters/

Problem:

Given a string str of length N, the task is to find the number of ways to insert only 2 pairs of parentheses into the given string such that the resultant string is still valid.

Example:

Input: str = “ab”Output: 6((a))b, ((a)b), ((ab)), (a)(b), (a(b)), a((b))which are a total of 6 ways.

Solution:

Approach: it can be observed that for the lengths of the string 1, 2, 3, …, N a series will be formed as 1, 6, 20, 50, 105, 196, 336, 540, … whose Nth term is (N + 1)2 * ((N + 1)2 – 1) / 12. 

The solution is good but the page does not provide derivation of the formula which is base of the solution.  I tried to derive the formula on my own and this is what I came up with:

1. There are N+1 places where parenthesis can be placed. One in the beginning, N-1 in middle and one at end. So there are   ((N + 1)4 )/4 ways to place the parenthesis. We can place multiple parenthesis at same location, one opening parenthesis can be replaced with another opening parenthesis and closing parenthesis can be replaced with other closing parenthesis therefore we divided by 4.
2. Some of the combinations counted in previous step are invalid so we need to subtract them. 
3. All four parenthesis at same location is not a valid case there are (N+1)/4  such combinations so we need to subtract them.
4. Three parenthesis being at one location and one being at one location is also not a valid combination. There are (N+1)*N/4 such combinations so we need to subtract them.
5. After the above considerations We come up with (N + 1)2 * ((N + 1)2 – 1) / 4 ways.
6. Now if you think closely out of following 6 possible combinations of parenthesis only first two are valid. You ignore string character in between parenthesis.
1. (())
2. ()()
3. )()(
4. )(()
5. ))((
6. ())(
7. So we need to divide by 3 to get valid ways of putting parenthesis. So we get the final formula as (N + 1)2 * ((N + 1)2 – 1) / 12.

An interesting Google interview question

Recently I read about an interesting Google interview question at https://www.geeksforgeeks.org/count-strings-can-formed-using-b-c-given-constraints/

The problem statement is:

Given a length n, count the number of strings of length n that can be made using ‘a’, ‘b’ and ‘c’ with at-most one ‘b’ and two ‘c’s allowed.

The page on GeeksForGeeks provide two programmatic solutions using recursion. But most interesting   one is mathematical one which directly calculate value. It took me quite long time to derive that formula. The formula is:

count = 1 + 2n+ n*((n*n)-1)/2 

Here I want to provide derivation for this formula. You may find it useful.

1. count of strings with no b's and no c's = 1
2. count of strings with one b and no c's = n
3. count of strings with no b's and one c = n
4. count of strings with one b and one c = n*(n-1)
5. count of strings with one b and two c's = n*(n-1)*(n-2)/2;
6. count of strings with no b and two c's = n*(n-1)/2

If you add all 6 values then you will get

count = 1 + 2n+ n*((n*n)-1)/2

The above formula works only for n greater than or equal to 3. 

The ACL permission error while exporting Cloud Watch logs to S3

Yesterday I struggled for more than 6 hours to export Cloud Watch logs to S3 bucket. I was getting the following error:

The ACL permission for the selected bucket is not correct. The Amazon S3 bucket must reside in the same region as the log data that you want to export. Learn more.

I tried following all the steps mentioned in the link but still it did not work. Later on I found the mistake, it interesting one so I am writing it in my blog so that you don't make same mistake.

The page https://docs.aws.amazon.com/AmazonCloudWatch/latest/logs/S3ExportTasksConsole.html

says that you need to set following policy to S3 bucket:

{
    "Version": "2012-10-17",
    "Statement": [
      {
          "Action": "s3:GetBucketAcl",
          "Effect": "Allow",
          "Resource": "arn:aws:s3:::my-exported-logs",
          "Principal": { "Service": "logs.us-west-2.amazonaws.com" }
      },
      {
          "Action": "s3:PutObject" ,
          "Effect": "Allow",
          "Resource": "arn:aws:s3:::my-exported-logs/random-string/*",
          "Condition": { "StringEquals": { "s3:x-amz-acl": "bucket-owner-full-control" } },
          "Principal": { "Service": "logs.us-west-2.amazonaws.com" }
      }
    ]
}

Here my-exported-logs is the bucket name and it needs to be replaced with your bucket name and us-west-2 needs to be replaced with your region code for Mumbai it is ap-south-1. 

The page says that random-string can be replaced with any random string which makes you believe that this string is not important but that is wrong. It is most important string for exporting logs to S3. The random string which you use in bucket permission needs to be provide as S3 bucket prefix while exporting logs to S3 bucket. If you don't provide S3 bucket prefix or provide a different prefix then you get the ACL error because the policy provide s3:PutObject permission only on random-string directory so if we try to put logs in some other directory then it will fail. The following export configuration works.

The only difference between working and not working dialog box is random-string being provided as S3 bucket prefix. I learned it the hard way by wasting 6 hours.