Goodness of a String

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
12 upvotes
Asked in companies
OracleeBayFlipkart limited

Problem statement

You are provided with a string ‘S’ which indicates the nested list. For example: “[1, [2, 3], [4, [5, 6] ] ]”. Each number present in the list has some depth. The depth of a particular number is the number of nested lists in which it is present. Consider the previous example in which the number ‘1’ is at depth 1, numbers ‘2’, ‘3’, and ‘4’ are at depth 2, and numbers ‘5’ and ‘6’ are at depth 3.

You have to find the goodness of the given string/nested list. The goodness of a string is the sum of the product of depths and elements present in the string.

For Example:

S = “[1, [2, 3], [4, [5, 6] ] ]”
Total depth  = 1*1 + 2*2 + 3*2 + 4*2 + 5*3 + 6*3 = 52

Note:

1. The given string may be empty. 
2. The string will not contain any white spaces. 
3. You have to take the modulo with 10 ^ 9 + 7 as the answer may be very large.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a string ‘S’ which denotes the given nested list.
Output Format: 
For each test case, print a single line containing a single integer denoting the goodness of the given string.

The output for every test case will be printed in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= |S| <= 100000
1 <= ES[ i ] <= 10^5

Where “|S|” is the length of the given string,  “ES[ i ]” is the element/number stored in the string at the “i-th” position.

Time limit: 1 sec
Sample Input 1:
2
[1,[2,3],[4,[5,6]]]
[[],[]]
Sample Output 1:
52
0
Explanation of sample input 1:
For the first test case, the explanation is given in the description.

In the second test case, the given string hasn’t contained any element/number therefore the goodness is equal to 0.
Sample Input 2:
3
[[[[[1,2,3,4,5]]]]]
[10,20,30,40]
[]
Sample Output 2:
75
100
0
Explanation for sample input 2:
In the first test case, all the numbers are at depth 5 and so the goodness is 1*5 + 2*5 + 3*5 + 4*5 + 5*5 = 75.

In the second test case, all the numbers are at depth 1 and so the goodness is 100.

In the third test case, there is no number present in the string.
Hint

While traversing the string maintain the current depth of the number and then keep track of the result.

Approaches (1)
Brute Force

The basic idea is to traverse through the complete string, make a variable to hold the current depth and whenever found a number just add it into our answer after multiplying it with the current depth.

 

The steps are as follows:

 

  1. Create two variables “depth” and “ans” to store the current depth and the answer. Initialize both of them with 0.
  2. Iterate through ‘s’. (say, iterator = ‘i’)
  3. Check if s[ i ] is ‘ , ’ then continue iterations.
  4. Else if, s[ i ]  is ‘ [ ‘ which means new depth has started and so, increment “depth” by 1.
  5. Else if, s[ i ] is ‘ ] ‘ which means one depth has ended and so, decrement “depth” by 1.
  6. Else, there must be a number at s[ i ] and so we have to take all the digits of this number.
    • Create a variable “num” that will be going to store the current number.
    • Iterate through ‘s’ again. (say, iterator = ‘j’)
      • If, s[ j ] becomes equal to ‘ , ‘ or ‘ ] ‘ which means the number has been already picked and so stop the further iterations.
      • Else, push this digit into “num”.
    • Multiply “num” with “depth” under modulo with 10^9 + 7 and then add the result into the “ans”.
    • Set ‘i’ to ‘j’ - 1 as the ‘j’ characters representing the number that has been already picked.
  7. Return “ans”.
Time Complexity

O(N), where ‘N’ is the total length of the string.

 

Since we are iterating through each character of the given string once and so the overall time complexity will be O(N).

Space Complexity

O(1).

 

Since we are not using any extra space and so, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Goodness of a String
Full screen
Console