Divided Palindromes Daily Coding Problem

Problem Statement

Given a list of words, find all pairs of unique indices such that the concatenation of the two words is a palindrome.

For example, given the list [“code”, “edoc”, “da”, “d”], return [(0, 1), (1, 0), (2, 3)].

This was Daily Coding Problem: Problem #1802 [Hard] from the daily coding problem email list.

Analysis

There is some vagueness about this problem. It mentions lists, but then talks about indices, which are the defining aspect of arrays. Lists, linked or not, are usually referenced by the first element of the list, and it’s much slower to find an arbitrary element of the list. I’ll go with arrays.

The statement doesn’t require any limits, like O(n) time, or O(1) additional space, but it does want pairs of indices.

The example gives extra info, “(0, 1)” and “(1, 0)” indicate they want you to find “codeedoc” and “edoccode”. You could easily read the text of the problem statement to mean that “(0, 1)” and “(1, 0)” would be some kind of equivalent.

There’s two algorithms to deal with, finding out whether a string is a palindrome, and iterating over the strings in the array correctly. Because the example says that “code” and “edoc” make two different palindromes, the iteration is a little harder.

Github repo for my code. I did this problem using the Go programming language, but a C or Java version wouldn’t look much different.

Palindromes

Commonly, “palindromes” are taken to ignore whitespace, so “race car” is often cited as a palindrome. This is a great place for a job candidate given this problem to ask a clarifying question. I assumed that that the input strings do not contain whitespace, but I’m not solving the problem in an interview, I have the luxury of ignoring this question.

I think it would be worth asking if a zero length string can occur in the input. It’s the identity element in string concatenation, so the possibility of zero length strings in the input could have consequences.

My code converts two input strings into Go []rune type slices, then concatenates the slices, so as to be able to use a simple palindrome check. It might be possible to write some super clever indexing-into-the-strings algorithm that could account for strings of different lengths to avoid the concatenation. I didn’t bother. My palindrome code is this:

func palindrome(a, b string) bool {
    runes := append([]rune(a), []rune(b)...)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        if runes[i] != runes[j] {
            return false
        }
    }
    return true
}

You only have to check character equality from either end to the middle of the string. It doesn’t hurt to compare from one end to the either, it’s just twice as many comparisons as strictly necessary.

I solved this problem using the Go programming language, which uses UTF-8 encoded Unicode strings internally. Indexing into a string yields a byte at the index. Converting a string to []rune convinces the Go runtime to create a structure with a character, or Unicode code point, at every index.

Assuming Unicode strings does lead you to some dark places. You should consider performing “NFC” normalization on Unicode input strings. It might be worthwhile to ask if byte-level or code point level palindromes are desired, and find out what character encoding is used.

Complexity

The number of concatenated strings to check to see if they’re palindromes should be the combinatoric _NP₂, which is N strings, permuted 2 at a time. A function implementing this problem would make n!/(n - 2)! or n² - n checks on the palindrome property.

I think that comes down to O(n²), where n is the number of input strings.

I wrote the looping like this:

    for i := 0; i < max; i++ {
        for j := 0; j < max; j++ {
            if i == j {
                continue
            }
            if palindrome(list[i], list[j]) {
                // save index pair (i, j)
            }
        }
    }

Even though it appears that only strings (i, j) get checked to see if they are palindromes when concatenated, the values of dummy variable j ranges from 0 to the maximum for every value of the dummy variable i. Whatever string made from indices (1,4) gets checked, and the string made from (4, 1) gets checked.

That arrangement of loop dummy variables did _NP₂. You could get _NC₂ (choose any 2 of 4 input strings) with loops like this:

    for i := 0; i < max; i++ {
        for j := i + 1; j < max; j++ {
            if palindrome(list[i], list[j]) {
                // save index pair (i, j)
            }
        }
    }

Comparing these two constructs also reveals an assumption I made: my code doesn’t check if a string concatenated with itself is a palindrome. The example includes the string “d” at index 3, but does not give index pair (3, 3) as part of the correct answer. Another subtlety overlooked in the problem statement that a candidate might ask about.

I had never discerned a relationship between combinatorics and looping in a computer program before doing this problem.

Empirically, since my code has a for-loop with a nested for-lop inside it, both iterating dummy variable from 0 to some N, I wrote an O(n²) time complexity program.

I think checking whether or not a string is a palindrome is O(m/2), where m is the number of characters in the string. I’m not sure how to combine these two measures of complexity.

This Problem in Job Interviews

This does not merit a “[Hard]” rating. There are two algorithms involved, checking for palindrome property, and iterating through the permutations of 2 strings out of N, but they’re both fairly simple. There are no data structures involved, other than a couple of arrays. This is a “[Medium]”.

I think an interviewer gets a opportunity to see a job candidate can write loops, and understood the difference between “2 strings out of N” and “permutations of 2 strings out of N” Candidates with a deeper understanding of character encoding in the implementation language might end up asking a lot more clarifying questions. If the interviewer is testing for Unicode knowledge, this problem might reveal something.