HackerRank: "Special Palindrome Again" Problem
2019-06-25

This article is part of a series exploring various coding exercises in depth.

Below I explain a few progressively-more-efficient solutions to the “Special Palindrome Again” problem. Note that they seem to have recently renamed it to “Special String Again” - I think that’s good, since the problem isn’t about palindromes. If you see references to “special palindrome” in discussions of this problem, just know that it means the same thing as what’s now referred to as a “special string”.

My solutions are written in Kotlin. I’ll just show how to implement the `substrCount` function; for the `main` function, I’m using the template HackerRank provides.

If you just want hints, without the full solution, see: June KC Code Challenge Hints.

Do you live in the Kansas City area & enjoy coding puzzles like these? Join me at the Kansas City Code Challenge meetup!

Table of Contents:

# O(N3) solution

A straightforward way to approach this problem is to break it into two subproblems:

1. Write a function to determine whether a given string is special.
2. Write a function that generates a list of all substrings of a given string.

Then you can easily check whether each substring is special, and record the total count of how many are.

## 1. Checking for specialness

The problem says a string counts as “special” if either all its characters are the same, or all the characters except the one in the middle are the same.

An algorithm to test for specialness would be:

1. Find the index of the middle character. For example, for a string of length 5 such as “fluff”, the middle index is 2 (the index of the first character is 0). For strings where the length is even, such as “food”, there is no middle index.
2. For each character in the string:
1. If this is the middle index, skip it; it doesn’t matter.
2. Otherwise, verify that it’s the same as the first character of the string.

Here’s a function for finding the middle index, which returns `-1` if there is no middle index:

``fun middleIndex(s: String) = if (s.length % 2 == 1) s.length / 2 else -1``

That says, simply, if the string has an odd-numbered length (the remainder is 1 when you divide its length by 2), then the middle index is the length divided by 2.

Using that, we can write our function to test whether a string is special:

``````fun isSpecial(s: String) = s.withIndex().all {
it.value == s || it.index == middleIndex(s)
}``````

`withIndex` allows us to operate on a list containing each character of the string along with that character’s index in the string. `all` tests each element of that list against a condition that we provide, and returns `true` if the condition returns `true` for all - not just some - of the elements. Our condition says that either the character must be equal to the first character of the string, or else this must be the middle index.

## 2. Generating all substrings

For the string “aab”, the list of all substrings is `["a", "aa", "aab", "a", "ab", "b"]`. The algorithm to generate that is:

• For each index i from 0 to length - 1:
• For each index j from i + 1 to length:
• Add the substring from i (inclusive) to j (exclusive) to the list.

Here’s code to do that, written in a functional style:

``````fun substrings(s: String) = (0 until s.length).asSequence().flatMap { i ->
((i + 1)..s.length).asSequence().map { j ->
s.substring(i, j)
}
}``````

Some things to notice:

• In Kotlin, `asSequence()` lets us operate on collections lazily. This means that when you call `substrings("aab")`, it won’t immediately construct a six-element list. Rather, each time you ask for another element from the list, it will generate that element right then. This way, we don’t actually have to keep all the substrings in memory at once, and our solution can have a space complexity of O(1).
• `flatMap` says that, for each entry in a given list (in this case, the list of indexes from 0 to length - 1), we’re going to generate a list of new elements, but we want them all combined into one output list. If we used `map` instead of `flatMap` here, the output of `substrings("aab")` would be `[["a", "aa", "aab"], ["a", "ab"], ["b"]]`.

## Combining the two functions

Now, we just have to count how many substrings are special:

``fun substrCount(n: Int, s: String) = substrings(s).count(::isSpecial).toLong()``

This says: find all substrings, then apply the `isSpecial` function to each of them, and count how many of them it returned `true` for.

## Why it’s O(N3)

Given a string of length N, the `substrings` function will generate a list that contiains N + (N - 1) + (N - 2) + (N - 3) … 1 elements. For large numbers, that is much closer to N2 than to N, so for simplicity we’ll say it generates N2 elements.

We call `isSpecial` on each of those elements, so the time complexity will be O(N2 * (time complexity of `isSpecial`)). `isSpecial` looks once at each character of the string it’s given, and we’ll be giving it strings of up to length N, so we can say its time complexity is O(N). That means the overall time complexity is O(N3).

# O(N2) solution

Consider how the previous solution handles the input string `"aab"`. The substrings are `["a", "aa", "aab", "a", "ab", "b"]`. Let’s think about how just the first three, `["a", "aa", "aab"]`, are handled. They’re all generated from the same starting index, 0, and each contains just one character appended onto the previous. But each call to `isSpecial` will look at every character in the substring again, even though the previous call to `isSpecial` already looked at all those characters except for the one new one at the end. That seems like wasted work; how can we optimize it?

Instead of generating all substrings, let’s just generate the substrings from each start index to the end of the string:

``fun tailStrings(s: String) = (0 until s.length).asSequence().map { s.substring(it) }``

Given `"aab"`, this will return `["aab", "ab", "b"]`. If we somehow write an O(N) function to determine how many specials a string starts with, then we can pass it each of those and we’ll have the total count of specials in O(N2) time. For example, if we can efficiently determine that `"aab"` starts with two specials - `"a"` and `"aa"` - we don’t need to worry about the additional special `"a"` in the middle, since we’ll detect that one later when we check the string `"ab"`.

To find the number of special strings at the start of a string, we need to consider the two types of special string.

Type 1: All the same character. It’s easy to figure out how many of these type-1 special strings are at the start of a string. We just loop through the characters until we find one that’s not equal to the first character. If the string starts with, say, 4 `'a'`s, then it starts with four type-1 special strings (`["a", "aa", "aaa", "aaaa"]`).

``````fun leadingCount(s: String, c: Char) = s.takeWhile { it == c }.length

fun leadingType1s(s: String) = leadingCount(s, s).toLong()``````

Type 2: All the same character except the middle. Once we know how many of the same first character there are at the beginning of the string, we can skip one character, then count out how many times the first character appears in a row after that. If that’s equal to or greater than the number at the beginning of the string, then there’s one type-2 special string at the start. For example, `"abaac"` starts with one type-2 special string (`"aba"`); `"aabac"` does not start with a type-2 special string (even though it contains one).

``````fun leadingType2s(s: String): Long {
val beforeMiddle = leadingCount(s, s)
val afterMiddle = leadingCount(s.drop(beforeMiddle + 1), s)
return if (afterMiddle >= beforeMiddle) 1 else 0
}``````

Now we can combine the `leadingType1s`, `leadingType2s`, and `tailStrings` functions to find the total number of special substrings:

``````fun leadingSpecials(s: String) = leadingType1s(s) + leadingType2s(s)

fun substrCount(n: Int, s: String) = tailStrings(s).map(::leadingSpecials).sum()``````

# O(N) solution

## Counting all consecutive characters

The previous solution is still doing a lot of redundant work. For example, given `"aaab"`, it will count how many leading `'a'`s there are in `"aaab"`, and then it will count how many leading `'a'`s there are in `"aab"`, and then how many in `"ab"`.

It would be much faster if we just went through the string once and built a list of how many times each character occurs in a row.

First, let’s define a data structure to hold a character and a count of its consecutive occurrences:

``data class CharCount(val char: Char, val count: Long)``

Then let’s write a function that loops through the string and emits a CharCount instance every time it encounters a character different from the previous character:

``````fun consecutives(s: String) = sequence {
var count = 1L
for (i in 1..s.length) {
if (i == s.length || s[i] != s[i-1]) {
yield(CharCount(s[i-1], count))
count = 0L
}
count++
}
}``````

This function returns a sequence, instead of a `List`, to minimize memory usage. In Kotlin, sequences can be lazily generated, meaning that each element is generated only when you ask for it, rather than generating the whole list up front and storing it in memory.

To understand how this works, let’s walk through what happens when you call `consecutives("aabaacc")`. The resulting sequence will have four elements: `[CharCount('a', 2), CharCount('b', 1), CharCount('a', 2), CharCount('c', 2)]`. This isn’t calculated immediately, though. The function returns an object of type `Sequence<CharCount>` immediately. Every time we ask for the next element in that sequence, the code in the block we provided to `sequence` will be executed until it calls `yield`. The parameter to `yield` is what will be used as the next element in the sequence.

So, the first time we ask for an element, `count` will be set to 1 and we’ll start iterating through the string. As soon as `i` is 2, we’ll notice that we’ve encountered a new character (`'b'`), so we will yield a `CharCount` instance containing the previous character (`'a'`) and the number of times we counted seeing it (2).

Then this block of code is suspended until another element is requested from the sequence. Once that happens, it will resume executing at the `count = 0L` line, and continue until it finds the next character change.

## Calculating type-1 special string counts

The problem specifies two types of special string we need to count. The first is where all the characters are the same.

If you know the length of a string and you know that it contains all the same character, then it doesn’t matter what that character is. The number of different substrings that can be formed depends entirely on the length:

• For `"a"`, there’s one (`["a"]`).
• For `"aa"`, there’s three (`["a", "aa", "a"]`).
• For `"aaa"`, there’s six (`["a", "aa", "aaa", "a", "aa", "a"]`)
• For length N, there are 1 + 2 + 3 + … + N-2 + N-1 + N. As explained on Wikipedia, there’s a simple way to calculate that sum: it’s equal to (N * (N + 1)) / 2.

So, using that formula and our sequence of consecutive-character counts from above, we can calculate the number of type-1 special strings efficiently:

``````fun sumToN(n: Long) = n * (n + 1) / 2
fun type1s(s: String) = consecutives(s).map { sumToN(it.count) }.sum()``````

## Calculating type-2 special string counts

The other type of special string consists of two strings that have all the same character, separated by a string of length 1 with a different character.

Using the sequence of consecutive character counts from above, we can efficiently find all the groups of three that contain type-2 special strings:

``````fun isType2Triplet(t: List<CharCount>) = t.count == 1L && t.char == t.char
fun type2Triplets(s: String) = consecutives(s).windowed(3).filter(::isType2Triplet)``````

`windowed(3)` gives us a sequence that contains groups of three elements starting from each element of the original sequence. To illustrate:

expression result
s `"aaabaacc"`
`consecutives(s)` `[CharCount('a', 3), CharCount('b', 1), CharCount('a', 2), CharCount('c', 2)]`
`consecutives(s).windowed(3)` `[[CharCount('a', 3), CharCount('b', 1), CharCount('a', 2)], [CharCount('b', 1), CharCount('a', 2), CharCount('c', 2)]]`

We then filter down that list to just those groups of three in which the first and third use the same character, and the middle is of length 1.

How do you figure out how many type-2 special strings are in each of those groups? Consider two examples:

• For `"aaabaa"` (represented by `[CharCount('a', 3), CharCount('b', 1), CharCount('a', 2)]`), there are 2: `"aba"` and `"aabaa"`.
• For `"abaa"` (represented by `[CharCount('a', 1), CharCount('b', 1), CharCount('a', 2)]`), there’s just 1: `"aba"`.

You can always form progressively longer type-2 special strings, working outward from the center, until one side or the other runs out of identical characters. So the number of type-2 specials is just the lesser of the character count on the left and the character count on the right:

``fun type2s(s: String) = type2Triplets(s).map { minOf(it.count, it.count) }.sum()``

## Putting it together

Now all we need to do is add the totals of the type-1 and type-2 special strings:

``fun substrCount(n: Int, s: String) = type1s(s) + type2s(s)``

Here’s the complete code again (excluding the `main` method, for which you can use the HackerRank template):

``````data class CharCount(val char: Char, val count: Long)

fun consecutives(s: String) = sequence {
var count = 1L
for (i in 1..s.length) {
if (i == s.length || s[i] != s[i-1]) {
yield(CharCount(s[i-1], count))
count = 0L
}
count++
}
}

fun sumToN(n: Long) = n * (n + 1) / 2
fun type1s(s: String) = consecutives(s).map { sumToN(it.count) }.sum()

fun isType2Triplet(t: List<CharCount>) = t.count == 1L && t.char == t.char
fun type2Triplets(s: String) = consecutives(s).windowed(3).filter(::isType2Triplet)
fun type2s(s: String) = type2Triplets(s).map { minOf(it.count, it.count) }.sum()

fun substrCount(n: Int, s: String) = type1s(s) + type2s(s)``````

## Why it’s O(N)

The `consecutives` function looks at each character of the string only once, making it O(N) time complexity.1 `map`, `sum`, `windowed`, and `filter` should all only need to look at each element of their input sequences once2, and emit at most one element for each input element3, so they don’t push our runtime beyond O(N).

The space complexity of this solution, if you ignore the memory used by the input string, is O(1)4. We’re never holding more than three CharCount instances in memory at a time.

Comments, questions, corrections? Email me at jacobaw@gmail.com

1. We do call it twice (from both `type1s` and `type2Triplets`), which is wasteful - you could refactor the program to only call it once - but this just adds a constant factor to the runtime (O(2N)), which is negligible when comparing against algorithms of O(N2), so we can ignore that in our analysis. [return]
2. `windowed(3)` presumably has to look at each element three times, but again, that’s a negligible constant factor. [return]
3. `windowed(3)` emits a list of three elements for each input element, but since that’s a constant size, it doesn’t affect this analysis. [return]
4. Assuming that `map`, `sum`, `windowed(3)`, and `filter` all are implemented in a way that uses O(1) space, which should be possible since we’re dealing with lazy sequences - they don’t need to store previous or subsequent elements (except for exactly 2 elements for `windowed`). [return]

Back to posts