Beautiful String

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.

We can use a stack to store the characters of “inputString”. We will iterate over the “inputString”. If it is ‘a’, we will push it to the stack , if it is ‘b’, we need to check the top of the stack. If the stack is empty, thus it will not be a “Beautiful String”. If the top of the stack is not ‘a’, then it will also not be a  “Beautiful String” as it can’t be substring “abc”. Otherwise, we will pop the element from stack and will push ‘b’ into the stack.

Similarly, if ‘c’ is encountered during the iteration, we need to check if the top of the stack is ‘b’ then we will pop the top element from the stack but we do not need to push ‘c’ back to the stack. The process continues until the string is all iterated, and at last, the stack should be empty which indicates the string “inputString” is a “Beautiful String”.

Note:

You can do this approach with the help of vector also in which during the iteration of “inputString”, if we encountered with ‘a’ or ‘b’ just simply push it into the vector and if the encountered element is ‘c’, just check if size of vector is not less than 2 or previous 2 elements in the vector should be ‘a’ and ‘b’ respectively. Then just simply pop the previous 2 elements from the vector and continue this process until full iteration. After iteration, just check if the vector is empty then return “True” to the function else “False”.

Algorithm:

• Create a stack “helperStack” .
• Create a boolean operator “isCheck” and set it as “True”.
• Now run an iteration from ‘i’ = 0 till the length of the string “inputString”.
• If the encountered element is ‘a’ OR ‘b’ then push it into the “helperStack”.
• If the encountered element is ‘c’
  • Check if “helperStack” is empty OR top element of “helperStack” is not equal to ‘b’
    • Make “isCheck” as “False” and break the iteration.
    • Pop the top element from stack
  • Check again if “helperStack” is empty OR top element of ”helperStack” is not equal to ‘a’
    • Make  “isCheck” as “False” and break the iteration.
    •  Pop the top element from stack
• Check if “isCheck” is “True” AND “helperStack” is empty then return “True” to the function else return “False”.

We can use two pointers, one pointer ‘iteratorPointer’ to traverse the string “inputString” and another pointer ‘searchPointer’ to find the substring “abc” in “inputString” (both pointers pointing to 0 initially).

• The idea is if ‘searchPointer’is greater than or equal to 3 then check last 3 elements of inputString before ‘searchPointer’contributing to substring “abc” or not
• if found, then decrement i by 3 and make inputString[searchPointer] = inputString[iteratorPointer] and continue finding substring “abc”.
• At last if ‘searchPointer’will be pointing to 0 then the given string “inputString” is a “beautiful String”.

Algorithm:

• First initialise pointer ‘searchPointer’ to 0
• Iterate pointer ‘iteratorPointer’ from 0 till length of the string “inputString”
  • Make every ‘searchPointer’th element of “inputString” equal to ‘iteratorPointer’th element of “inputString”
  • Increment pointer ‘searchPointer’ by value = 1
  • Check if ‘searchPointer’ is greater than or equal to 3 and if previous elements contributing to substring “abc” or not
    • searchPointer > = 3 && inputString[searchPointer - 3] == 'a' && inputString[searchPointer - 2] == 'b' && inputString[searchPointer - 1] == 'c'
      • If found then decrement the pointer ‘searchPointer’ by value 3.
• After iteration, check if the pointer ‘searchPointer’ is pointing to 0 or not.
• If pointing to 0 then return true else return false.