Beautiful String

Posted: 26 Apr, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.

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
Approach 1

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.
Try Problem