The Worst Code Challenge Question
This is a clickbaity title, but this was easily the most difficult code challenge problem that I have solved yet. This is in no way the most efficient solution to this problem, but it works. I am very interested if anyone reading this knows of a more elegant solution to this problem. Feel free to shoot me a message on any of the contact links on my site if you have a better answer. I will detail my thought process in this post.
The Premise
Given an input of 3 integers, like 6, 1, 1, that are associated with numbers of the letters, a, b, c, make a string that places the letters without more than 2 letters repeating in a row. For 6, 1, 1, the desired output will be aabaacaa. Assume that the input will allow a straightforward answer and won’t make a valid answer impossible. For example, 0, 0, 3 wouldn’t work because ccc has 3 c’s in a row.
First Try
function solution(A, B, C) {
let str = ""
let stackA = []
let stackB = []
let stackC = []
let total = A + B + Cfor(let i = 0; i < A; i++){
stackA.push("a")
}for(let i = 0; i < B; i++){
stackB.push("b")
}for(let i = 0; i < C; i++){
stackC.push("c")
}for (let i = 0; i < total; i++) {
if (stackA.length > 0 && str[i-2] !== "a") {
str += stackA[0]
stackA.pop()
} else if (stackB.length > 0 && str[i-2] !== "b") {
str += stackB[0]
stackB.pop()
} else if (stackC.length > 0 && str[i-2] !== "c") {
str += stackC[0]
stackC.pop()
} else {
if (stackA.length > 0) {
str += stackA[0]
stackA.pop()
} else if (stackB.length > 0) {
str += stackB[0]
stackB.pop()
} else if (stackC.length > 0) {
str += stackC[0]
stackC.pop()
}
}
}return str
}console.log(solution(6, 1, 1)) //aabcaaaa
console.log(solution(6, 2, 2)) //aabbaaccaa
console.log(solution(2, 4, 2)) //aabbccbb
Analysis
I had quite a bit of difficulty with thinking how to approach this problem until I thought about what kind of data structure would allow me to place letters when I needed them. I decided to go with a queue because it allowed me to track the number of letters and shift out a letter from each letter’s queue until they were empty. I added up the inputted numbers to get a total number to iterate through. I concatenated a letter to an outputted string and shifted out the letter from the queue once it was used. The else statement checks for edge cases. I checked to make sure that the letter wasn’t used in the output string 2 indexes back. This solution was incomplete because if there weren’t all even numbers in the input, like in 6, 1, 1, it wouldn’t work. It outputted aabcaaaa, with aaaa being invalid.
It was time to go back to the drawing board…
Final Answer
I know that this is a lot to take in, but I will break it down in detail below.
let dubs = []
let singles = []function solution(A, B, C) {
let str = ""
dubs = []
singles = []
let leftovers = []
let strArr = []
let total = A + B + Clet counts = {"a": A, "b": B, "c": C}
// avoids edge cases where multiple dubs can be added at the end of the string
let sortedCounts = Object.keys(counts).sort((a,b) => counts[b] - counts[a])for (let letter in sortedCounts) {
placeLetters(counts[sortedCounts[letter]], sortedCounts[letter])
}
// placeLetters(A, "a")
// placeLetters(B, "b")
// placeLetters(C, "c")// str and strArr are used because it's easier for me to keep track // of what's valid and invalid in a string vs an arr
for (let i = 0; i < total; i++) {
// keeps track of dubs that are valid to be in str
if (dubs.length > 0 && dubs[0] !== str.slice(-2)) {
str += dubs[0]
strArr.push(dubs[0])
dubs.shift()
// pushes invalid dubs into leftovers
} else if (dubs[0] === str.slice(-2)){
leftovers.push(dubs[0])
dubs.shift()
}
// pushes valid single letters into strArr
if (singles.length > 0 && singles[0] !== str.slice(-1)) {
str += singles[0]
strArr.push(singles[0])
singles.shift()
}
}// places leftover dubs into strArr in valid places
if (leftovers.length > 0) {
for (let i = 1; i < strArr.length+1; i++) {
if (strArr[i-1] !== leftovers[0] && leftovers.length > 0) {
strArr.splice(i, 0, leftovers[0])
leftovers.shift()
}
}
}str = strArr.join("")
return str
}function placeLetters(count, letter) {
if (count === 0) {
return
}
// handles even numbers
if (count/2 > 1 || count === 2) {
for(let i = 0; i < Math.floor(count/2); i++){
dubs.push(letter + letter)
}
// handles 1 letter if there are even numbers existing
if (count % 2 > 0) {
singles.push(letter)
}
// handles odd numbers if there are no even numbers
} else {
singles.push(letter)
}
}console.log(solution(6, 1, 1)) // aabaacaa
console.log(solution(1, 6, 1)) // bbabbcbb
console.log(solution(1, 1, 6)) // ccaccbcc
console.log(solution(6, 2, 2)) // aabbaaccaa
console.log(solution(2, 4, 2)) // bbaabbcc
console.log(solution(2, 3, 2)) // bbaabcc
console.log(solution(1, 3, 6)) // ccbccaccbb
console.log(solution(3, 4, 3)) // bbabbcaacc
console.log(solution(1, 1, 2)) // ccab
console.log(solution(0, 0, 2)) // cc
Analysis
let str = ""
dubs = []
singles = []
let leftovers = []
let strArr = []
let total = A + B + Clet counts = {"a": A, "b": B, "c": C}
// avoids edge cases where multiple dubs can be added at the end of the string
let sortedCounts = Object.keys(counts).sort((a,b) => counts[b] - counts[a])for (let letter in sortedCounts) {
placeLetters(counts[sortedCounts[letter]], sortedCounts[letter])
}
// placeLetters(A, "a")
// placeLetters(B, "b")
// placeLetters(C, "c")
I decided to go with a slightly different approach with this problem than the first try. Instead of putting each letter into their own queues, I made a queue for 2 letters called dubs and a queue for 1 letter called singles. I made a counts object with the letter counts and sorted them in descending order to avoid having to deal with edge cases where multiple double letters are added to the end of output string.
function placeLetters(count, letter) {
if (count === 0) {
return
}
// handles even numbers
if (count/2 > 1 || count === 2) {
for(let i = 0; i < Math.floor(count/2); i++){
dubs.push(letter + letter)
}
// handles 1 letter if there are even numbers existing
if (count % 2 > 0) {
singles.push(letter)
}
// handles odd numbers if there are no even numbers
} else {
singles.push(letter)
}
}I made this placeLetters function to place the letters into the dubs and singles queues (both are global variables) based on whether or not the counts for each letter were divisible by 2. The divisible by 2 counts are pushed into dubs and the odd numbers are pushed into singles. Anything with a 0 count returns null.
// str and strArr are used because it's easier for me to keep track // of what's valid and invalid in a string vs an arr
for (let i = 0; i < total; i++) {
// keeps track of dubs that are valid to be in str
if (dubs.length > 0 && dubs[0] !== str.slice(-2)) {
str += dubs[0]
strArr.push(dubs[0])
dubs.shift()
// pushes invalid dubs into leftovers
} else if (dubs[0] === str.slice(-2)){
leftovers.push(dubs[0])
dubs.shift()
}
// pushes valid single letters into strArr
if (singles.length > 0 && singles[0] !== str.slice(-1)) {
str += singles[0]
strArr.push(singles[0])
singles.shift()
}
}This part is a bit convoluted and could use some refactoring, but it works. I populate the str string and strArr array with valid letters from the dubs and singles queues. I used strings and arrays because I was having problems keeping track of valid and invalid string combinations with just an array, so I used strings for the conditional statements. Valid strings are pushed into strArr and the queues are shifted. Invalid dubs are pushed to a leftovers queue so that they can be placed later. This was the solution to the 6, 1, 1problem that I had on the first try, where it outputted aabcaaaa, with aaaa being invalid and thus leftovers. Everything up to this point works with just even numbers, like 6, 2, 2 that outputs aabbaaccaa.
// places leftover dubs into strArr in valid places
if (leftovers.length > 0) {
for (let i = 1; i < strArr.length+1; i++) {
if (strArr[i-1] !== leftovers[0] && leftovers.length > 0) {
strArr.splice(i, 0, leftovers[0])
leftovers.shift()
}
}
}str = strArr.join("")
return str
}
The leftover dubs are pushed into strArr when they are valid and not preceded by 2 of the same letters before it. The queue is shifted after each dub is placed. Lastly, strArr is joined and overwrites str to give us our output. This part makes 6, 1, 1 finally give us aabaacaa.
Thanks for reading!
