Longest Happy String

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
6 upvotes
Asked in companies
SalesforceWalmartVFISLK Global Services

Problem statement

Ninja likes to play with strings, and he calls a string ‘S’ Happy if it only contains letters ‘a’, ‘b’, and ‘c’, and no three consecutive letters in the string are the same. For example, ‘aa’, ‘aab’, ‘aabbcc’ are the happy strings, but ‘aaa’, ‘aaza’, ‘aaabbb’ are not happy strings.

You are given three non-negative integers ‘X’, ‘Y’, ‘Z’. You need to find the longest happy string such that it contains ‘a’ at most ‘X’ times, ‘b’ at most ‘Y’ times, and ‘c’ almost ‘Z’ times.

Note:

There can be more than one possible string with maximum size. In that case, you can return any of them.
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 first line of each test case contains three space separated integers, ‘X’, ‘Y’, and ‘Z’, which denote the maximum number of ‘a’, ‘b’, and ‘c’ respectively answer strings can have.

Output Format:

For each test case, the output will be “1” if you have returned the correct answer, else it will be “0”.

Note :

You do not need to input or print anything, and it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
0 <= X, Y, Z <= 10^3
X + Y + Z >= 1

Time Limit: 1 sec

Sample Input 1:

2
2 4 4
6 1 1

Sample Output 1:

1
1

Explanation of Sample Input 1:

Test case 1:
For the first test case one of the possible string is “aabbccbbcc”, other possible string can be “abbccbbcca” or “bbcabbcacc”. All these strings have maximum possible length equal to 10, and no three consecutive letters are the same.

Test case 2:
For the second test case, one possible answer string is “aabaacaa” of length 8, another possible string is “aacaabaa”.

Sample Input 2:

1
6 0 1

Sample Output 2:

1

Explanation of Sample Input 2:

Test case 1:
There is only one possible string for the first test case i.e. “aacaa” of length 5.
Hint

Check all possible strings

Approaches (3)
Brute Force Approach

Given 'X', 'Y' 'Z' you can try all combinations of possible strings and return the string that has a maximum length. You can create all possible strings by inserting all the three letters i.e. ‘a’, ‘b’, ‘c’ at each ‘i -th’ position in string by taking care of the condition that no three characters should be the same. For example at ‘i -th’ position in the string you can add the letter ‘a’, if and only if 'X' greater than 0 and the last two letters in string i.e. at position ‘i - 1’ and ‘i - 2’ are not ‘a’. Similarly of ‘b’ and ‘c’. At last check all the possible strings you generated and return the string with the maximum size.

 

Algorithm:

 

  • Declare a global empty string, say 'ANSWER'.
  • Create a function say 'FIND_LONGEST' to generate and find the maximum possible string.
  • Create a function say ‘check’ to check if a character can be added in a string or not.
  • Call 'FIND_LONGEST' with given 'X', 'Y', 'Z' and 'ANSWER'.
  • Return answer.

 

Description of ‘check’ function

 

The function will take two parameters:

  • 'STR': Current string.
  • ‘c’:  character to add.

bool check( 'STR', ‘c’ ):

  • If the size of 'STR' is less than 2, then we can add any character, So return true.
  • If last two characters are same as ‘c’, then return False,
  • Else return True.

 

Description of 'FIND_LONGEST' function

 

The function will take four parameters:

  • ‘X’ : The maximum number of ‘a’ can be added.
  • ‘Y’ : The maximum number of ‘b’ can be added.
  • ‘Z’ : The maximum number of ‘c’ can be added.
  • 'STR': Current string.

void findLongest ( ‘X’, ‘Y’, ‘Z’, 'STR' ):

  • If the size of 'STR' is greater than the size of 'ANSWER', then update answer.
    • 'ANSWER' = 'STR'
  • If ‘X’ > 0 and check('STR', ‘a’) is true i.e. we can add ‘a’ to current 'STR'.
    • Recursively call ‘findLongest (X - 1, Y, Z, 'STR' + ‘a’ )’.
  • If ‘Y’ > 0 and check('STR', ‘b’) is true i.e. we can add ‘b’ to current 'STR'.
    • Recursively call ‘findLongest (X, Y - 1, Z, 'STR' + ‘b’ )’.
  • If ‘Z’ > 0 and check('STR', ‘c’) is true i.e. we can add ‘c’ to current 'STR'.
    • Recursively call ‘findLongest (X, Y, Z - 1, 'STR' + ‘c’ )’.
Time Complexity

O(3 ^ (X + Y + Z)), where 'X', ‘Y’, ‘Z’ are the given maximum number ‘a’, ‘b’, and ‘c’ respectively that the output string can have.

 

As we are checking every possible string upto total length which is ‘(X + Y +Z)’, and at every ‘i-th’ position there can be 3 characters possible i.e ‘a’, ‘b’ and ‘c’ so the total strings possible in worst case are 3 ^ (X + Y + Z). Hence the over time complexity is O (3 ^ (X + Y + Z)).

Space Complexity

O(X + Y + Z), where ‘X’, ‘Y’, ‘Z’ are the given maximum number ‘a’, ‘b’, and ‘c’ respectively output string can have.

 

In the worst case, we need to store a string of size ‘X + Y +Z’, that takes O (X + Y + Z) space. Hence the space complexity will be O (X + Y +Z).

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