InterviewQ: LongestCharSeq Solution

This is part of my ongoing Interview Guide where I log my journey to Software Engineering Wizardom.

Here’s the question prompt as it appeared in my January 2016 Interview Questions post:

---

Create a function that takes in a String and returns the largest consecutive sequence of characters greater than 1 in that String. A consecutive sequence is one where each character comes after the character that came before it in the string in the alphabet e.g. “abc”.

Sample cases:

• “abxy” -> “ab”
• “abc” -> “abc”
• “a” -> “”
• “abdef” -> “def”

---

You can find my solution on GitHub.

I’m making assumptions that we won’t be passed a null string, that all chars are letters in the English alphabet, and that the given string is more than one character in length.

I first initialize a StringBuffer result which is where we’ll store the best solution we’ve come up with. I then call s.toLowerCase() to standardize our input and initialize the lastChar variable – which will help determine whether the character we’re looking at is valid or not – to the first character in the given’s string value – 1. Initializing it to s.charAt(0) – 1 ensures that the first character of the string is seen as valid in the for loop.

The reason I’m using a StringBuffer is because the .append() method performs a lot faster than the standard string concatenation using “+=”. I’m not going to go too deep into this, but the “+=” defaults to copying the entire string over, whereas .append() just adds the char to an internal data structure. So what we lose in increase memory use for StringBuffer, we often gain back in performance assuming this sort of concatenation will be performed often.

The For Loop

The for loop iterates through the string. If the character we’re looking at comes directly after the previous character we looked at in the ASCII numbering scheme, then we add that character to our currentSeq StringBuffer and update the lastChar variable to hold our currChar value (so that the next check works as it should).

If the character we’re checking isn’t the next character in the alphabet, then we check if our currentSeq StringBuffer is larger than result – or the largest valid sequence we’ve found. If it is, we set result equal to currentSeq. If not, result stays the same. Regardless, we clear currentSeq by setting it equal to a new StringBuffer() so that future checks aren’t interfered with by our old, now invalid, data.

Notice that we only check if the currentSeq is larger than result if we find a character that doesn’t belong (and once right before we return). This ensures that we aren’t checking this every single time we add a letter, only when necessary – an efficiency optimization.

At the very end, we make a final check between result and currentSeq to see if result should be replaced. Then we return result.toString().

You can find my implementation below:

(https://gist.github.com/SIRHAMY/25f2fe34129d98c007f2)