Beautiful String

Moderate
0/80
Average time to solve is 30m
2 upvotes
Asked in companies
SAP LabsAmazonJaguar Land Rover

Problem statement

Suppose we are given an empty string “inputString”. We have to convert this “inputString” into a “Beautiful String”

We can perform any number of operations on “inputString” to convert it to “Beautiful String”.

Operation :

You have to insert “abc” to “inputString” in every operation.
If “inputString” is empty just insert “abc” in “inputString”
If “inputString” is not empty, you can insert “abc” in any position in “inputString” in such a way that:
1. “ LEFT PORTION OF “inputString” ” + “ abc ” + “ RIGHT PORTION OF “inputString” ” = “Beautiful String”.
2. “ LEFT PORTION OF “inputString” ” maybe EMPTY OR “a” OR “ab” OR “abc”.
3. “ LEFT PORTION OF “inputString” ” maybe EMPTY OR “c” OR “bc” OR “abc”.

Your task is to find whether the given string “inputString” is a “Beautiful String”, or not.

Note : 
The given string "inputString" cannot be empty.
Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The next line of each test case contains a string “inputString”, representing the string for which you have to determine if the string is a “Beautiful String” or not.

Output Format :

For each test case, print a single line as “True” or “False”  as per the given condition.

The output of each 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 <= |inputString| <= 1000  

Where “inputString” will have only lowercase alphabets and |inputString| represents the length of the input string.

Time Limit: 1 sec

Sample Input 1 :

2
abcabc     
abccba

Sample Output 1 :

True
False
Explanation of Sample Input 1 :
Test Case 1 :
For the first test case, the given string is “abcabc” so we return “True” as first we add “abc” then again “abc” so we can say we are able to build the string “inputString” to “Beautiful String”.

Test Case 2 :
For this test case, the given string is “abccba” so we return “False” as first we add “abc” then we can’t add “abc” as “cba” is present so we return false.

Sample Input 2 :

2
aabcbc
babcc

Sample Output 2 :

True
False
Hint

Can you think of a Brute Force approach?

Approaches (3)
Brute Force

The idea is to insert “abc” at every position in a string , “helperString” (initialised as an empty string) recursively and comparing it with the input string “inputString” at every recursive step. If the “helperString” comes out to be equal to input string “inputString” then return “True” to the function else “False”.

 

Algorithm:

 

  • First make a recursive boolean  function “Solve” and pass “helperString” and “inputString” in its arguments.
  • Make a base condition that if the length of “helperString” becomes greater than the length of “inputString” then return “False” to the function.
  • Compare both the strings “helperString” and “inputString” when length of “helperString” becomes equal to the length of “inputString”
    • If both the strings “helperString” and “inputString” are equal then return “True” to the function.
  • Make a boolean variable “ans” to store the answer.
  • If “helperString” is empty (i.e in the initial phase) then call the “Solve” function recursively sending “inputString” and “abc” as arguments and store it in “ans”.
  • Now, make an iteration from ‘i’ = 1 till the length of “helperString”.
    • Make a string ‘s’ inside the iteration to store the string with “abc” at every position in “helperString”.
    • If ‘i’ will reach the last index of “helperString” then just simply insert “abc” in “helperString” and store the modified string “helperString” in ‘s’.
    • If ‘i’ will be at some random position of “helperString” then insert “abc” at that random position and store the modified string “helperString” in ‘s’.
    • Now, call the “Solve” function recursively, passing “inputString” and ‘s’ as its arguments and store it in “ans”.
  • Return the “ans” to the function.
Time Complexity

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

 

As we are calling the recursive function for every possible position in the generated string,  so overall time complexity becomes equal to O(N ^ N).

Space Complexity

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

 

Since we are using an additional string that will be of maximum length equal to that of the input string, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Beautiful String
Full screen
Console