Longest Happy String Solution
Understand Leetcode Longest Happy String(1405) With Brute Force and Optimal Solution
This document presents the solution to the problem 1405. Longest Happy String. We’ll first look into a very simple brute force approach then we’ll optimize the solution and come up with a better solution. Due to this approach you’ll find the approach for Filling Bookcase Shelves to be similar as well.
Note: Make sure to go through the code comments as well. It’ll help you understand the concept better.
A string is called happy if it does not have any of the strings 'aaa', 'bbb' or 'ccc' as a
substring.
Given three integers a, b and c, return any string s, which satisfies following conditions:
- s is happy and longest possible.
- s contains at most a occurrences of the letter 'a', at most b occurrences of the letter
'b' and at most c occurrences of the letter 'c'.
- s will only contain 'a', 'b' and 'c' letters.
If there is no such string s return the empty string "".
Example 1:
Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.
Example 2:
Input: a = 2, b = 2, c = 1
Output: "aabbc"
Example 3:
Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It's the only correct answer in this case.
Constraints:
0 <= a, b, c <= 100
a + b + c > 0
Let’s start with a simple brute force approach for this input:
var a int = 2
var b int = 2
var c int = 1
The values for a, b and c represent a state and, the current state can be represented as
State:
String: ""
a = 2, b = 2, c = 1
So for the input (a = 2, b = 2, c = 1), this is Brute Force approach I came up with:
- Start from the input state.
- If
a > 0then pick the charactera, reduce the count for variableaand create a new state. - If
b > 0then pick the characterb, reduce the count for variableband create a new state from the input state. - If
c > 0then pick the characterc, reduce the count for variablecand create a new state from the input state. - This way I have three new states. They are:
State 1:
String: "a"
a = 1, b = 2, c = 1
State 2:
String: "b"
a = 2, b = 1, c = 1
State 3:
String: "c"
a = 1, b = 2, c = 0
- Now, I’ll consider each of the new states as the input state and restart from step 1.
- While picking the character I’m also making sure I don’t create a substring like
aaa,bbbandcccand they are omitted the moment I find them.
So, after the first round I get these three string:
"a""b""c"
Then from "a" I get:
"aa""ab""ac"
similarly, I get "ba", "bb" and "bc" from "b" and "ca", "cb" from "c". No "cc"" because the c's count
became 0 after it was used once.
Here is the graph that shows how each of the states are getting created:
Due to the complexity of the image, I’ve kept the data for first three levels only. You can see here that iterating over the states can keep on producing new string for us and in the end we’re reaching to a string that cannot be extended any further because:
- the count of a, b and c becomes 0
- any new combination cannot be made, for example, if the input is 0, 0, 100, the only possible output is
"cc"as I cannot add anymore"c".
While this approach works fine, it has a very high space complexity of O(3n). So, let’s try to come up with a better solution.
***
So, in this solution I looked into all the possible options because I didn’t know if that option is correct or not and this is why the space complexity was so high. Let’s look into one more way to solve it with a new input, a = 1, b = 2 and c = 7.
So, at the start the string is blank, and the current state is:
State:
String: ""
a = 1, b = 2, c = 7
Now, let’s pick c as it has the max count. Also, I’ll be picking up two c's this time.
So, our state is:
State:
String: "cc"
a = 1, b = 2, c = 5
Now, I cannot pick c because that will make the string cccc and that is invalid so instead of that I’ll pick b
because it has more count than a. So, our state becomes
State:
String: "ccbb"
a = 1, b = 0, c = 5
Then, I’ll pick c because of the count, and the state is:
State:
String: "ccbbcc"
a = 1, b = 0, c = 3
Now, I cannot pick c but I can pick a so the state after adding a:
State:
String: "ccbbcca"
a = 0, b = 0, c = 3
Then I can pick c because the last character is a so I won’t get an invalid string:
State:
String: "ccbbccacc"
a = 0, b = 0, c = 1
Now, here’s the interesting part. Where can I put the last c in the string? It cannot be appended in the last because
there are two c's already present. So, I’ll just put it in between the two b's.
State:
String: "ccbcbccacc"
a = 0, b = 0, c = 0
And with that adjustment, we’ve reached to the solution!
Here’s the algorithm that I’ve used:
- Find the character with most occurrences.
- Find the character that is at the end.
- If characters from the step 1 and 2 match then
- Find character with second most occurrence
- If found
- Pick two of them if their count >= 2 otherwise pick 1.
- Append to the string
- If not found
- Adjust the character from step 1 in the string and stop the execution of code if adjustment is not possible
- If found
- Find character with second most occurrence
- If characters from the step 1 and 2 do not match then
- Pick two of them if their count >= 2 otherwise pick 1.
- Append them to the string
Now, we can proceed to the code. Here’s the code present on GitHub as well:
func longestDiverseString(a int, b int, c int) string {
var countMap = map[uint8]int{
'a': a,
'b': b,
'c': c,
}
diverseString := ""
for {
currentOrder, cont := findLargest(countMap['a'], countMap['b'], countMap['c'])
if !cont {
return diverseString
}
if len(diverseString) == 0 {
// Just append if the string is blank
// It means we've just started
diverseString = appendToString(countMap, currentOrder, 0, diverseString)
continue
}
// this block will be executed if the last character is also the character with most occurrences
// This part of the code means we're currently at 3rd step of the algorithm
if diverseString[len(diverseString)-1] == currentOrder[0] {
if countMap[currentOrder[1]] > 0 {
// append the second most greatest
diverseString = appendToString(countMap, currentOrder, 1, diverseString)
} else if countMap[currentOrder[2]] > 0 {
// otherwise append the third most greatest
diverseString = appendToString(countMap, currentOrder, 2, diverseString)
} else {
// this block is executed there is not any other character to fill up the string
// so here I'm adjusting the character.
added := false
for i := 0; i < len(diverseString)-1; i++ {
if diverseString[i] != currentOrder[0] && diverseString[i+1] != currentOrder[0] {
if countMap[currentOrder[0]] == 1 {
diverseString = diverseString[:i+1] + string(currentOrder[0]) + diverseString[i+1:]
countMap[currentOrder[0]]--
} else {
diverseString = diverseString[:i+1] +
string(currentOrder[0]) + string(currentOrder[0]) +
diverseString[i+1:]
countMap[currentOrder[0]] -= 2
}
added = true
break
}
}
if !added {
return diverseString
}
}
} else {
// this block is the point 4 of the algorithm
diverseString = appendToString(countMap, currentOrder, 0, diverseString)
}
}
}
func appendToString(countMap map[uint8]int, currentOrder [3]uint8, index int, diverseString string) string {
if countMap[currentOrder[index]] == 1 {
diverseString += string(currentOrder[index])
countMap[currentOrder[index]]--
} else {
diverseString += string(currentOrder[index]) + string(currentOrder[index])
countMap[currentOrder[index]] -= 2
}
return diverseString
}
func findLargest(a, b, c int) ([3]uint8, bool) {
if a <= 0 && b <= 0 && c <= 0 {
return [3]uint8{}, false
}
if a >= b && a >= c {
if b >= c {
return [3]uint8{'a', 'b', 'c'}, true
} else {
return [3]uint8{'a', 'c', 'b'}, true
}
} else if b >= a && b >= c {
if a >= c {
return [3]uint8{'b', 'a', 'c'}, true
} else {
return [3]uint8{'b', 'c', 'a'}, true
}
} else {
if a >= b {
return [3]uint8{'c', 'a', 'b'}, true
} else {
return [3]uint8{'c', 'b', 'a'}, true
}
}
}
The function findLargest returns an array of characters(a, b and c) sorted on their occurrence, and the function
appendToString appends the character at the index, index, to the string. Once I find that no more characters can
be added then the loop is exited, and the string is returned.
