LESSON 251 OF 415 · TWO POINTERS

Palindrome Substrings in Swift: Brute Force with Two Pointers, O(n³)

Practice O(n³) Read the full explanation

Given a string, count the number of palindromic contiguous substrings in the string.

The substrings with different start indexes or end indexes are counted as different substrings even if they consist of same characters.

Example:

Input:  "abbcbc"

Output: 9

Explanation: ["a", "b", "b", "c", "b", "c", "bb", "bcb", "cbc"]

STEP 1 OF 11

Guided

Ctrl + Enter to check

Palindrome Substrings in Swift, explained

Problem overview

The method countPalindromes receives a string, input, and returns how many of its contiguous substrings are palindromes. Substrings with different start or end positions count separately, even when they spell the same text.

For "abbcbc" the answer is 9. The palindromic substrings are "a", "b", "b", "c", "b", "c", "bb", "bcb" and "cbc". The two "b" substrings at positions 1 and 2 are two entries, and so are the "c" substrings at positions 3 and 5.

Approach: check every substring

A substring is fixed by its first index i and its last index j, with i <= j. A string of length n has about n²/2 of them. This lesson tests each one: for every pair (i, j), a helper decides whether the substring is a palindrome, and the counter grows by one when it is.

The helper uses two pointers. It compares the characters at the two ends, then moves both pointers toward the middle, and answers false on the first mismatch. A single character is always a palindrome, because the pointers start on the same index and the loop doesn't run.

This is the brute-force approach. A later lesson on the same problem counts palindromes around their centers and avoids the repeated work, because the substrings checked here overlap heavily.

For "abbcbc" the loops visit all 21 substrings. By length, the six substrings of length 1 all pass, and the only passing substring of length 2 is "bb". Of length 3, "bcb" and "cbc" pass, while "abb" and "bbc" fail. Nothing longer passes. That makes 6 + 1 + 2 = 9.

Step by step

Convert the string to bytes. Swift strings can't be indexed with integers, so let bytes = Array(input.utf8) makes an array of UInt8 values. n is its count, and result is a var starting at 0.
Loop i over 0..<n, the first index of the substring.
Loop j over i..<n, the last index. Starting at i allows one-character substrings.
Test the substring. Write an if that calls isPalindrome(bytes, i, j), and add 1 to result when it returns true. The helper doesn't exist yet at this point; the lesson writes it afterwards.
Return result after both loops.
Declare the helper above countPalindromes: isPalindrome takes the byte array and two indices, left and right, and returns a Bool.
Copy the indices. Parameters in Swift are constants, so var l = left and var r = right give you pointers you can move.
Loop while l < r. The pointers walk toward the middle.
Compare the ends. If input[l] != input[r], return false: this substring is not a palindrome.
Move both pointers. l += 1 and r -= 1.
Return true after the loop, because every pair matched.

The solution in Swift

class Solution {
    func isPalindrome(_ input: [UInt8], _ left: Int, _ right: Int) -> Bool {
        var l = left
        var r = right
        while l < r {
            if input[l] != input[r] {
                return false
            }
            l += 1
            r -= 1
        }
        return true
    }

    func countPalindromes(_ input: String) -> Int {
        let bytes = Array(input.utf8)
        let n = bytes.count
        var result = 0
        for i in 0..<n {
            for j in i..<n {
                if isPalindrome(bytes, i, j) {
                    result += 1
                }
            }
        }
        return result
    }
}

Swift details worth knowing:

The helper's parameter is named input. It is the byte array here, not the original string. Inside isPalindrome, input[l] is a UInt8, and bytes compare with != directly.
input.utf8 is a view of the string's UTF-8 bytes. Array(input.utf8) copies it into a [UInt8] that can be indexed. For "abbcbc" it is [97, 98, 98, 99, 98, 99].
Bytes versus characters. For ASCII text, such as the lesson's lowercase letters, one byte is one character, so counting bytes is the same as counting characters. A non-ASCII character takes several bytes: "é" takes 2, and "日" takes 3. For "é" this code returns 2, one per byte, although the string has one palindromic substring. It is right for ASCII input only. The center-expansion version in the other lesson, which uses Array(input) and compares Character values, returns 1.
Passing arrays is cheap. Swift copies an array's storage only when something changes it. isPalindrome only reads input, so each call shares the same storage.
Parameters are constants. Assigning to left or right inside the helper doesn't compile. That is why the copies l and r exist.

Complexity

Time: O(n³). There are about n²/2 pairs (i, j), and checking a palindrome takes up to (j - i + 1) / 2 comparisons, which can reach n / 2. A string of one repeated letter is the worst case, because no check ends early.

Space: O(n). The byte array holds n values. The helper adds only a few integers.

Edge cases and common mistakes

Empty string. n is 0, the loop 0..<0 is empty, and the method returns 0.
One character. "a" returns 1.
All different characters. "abc" returns 3, only the single letters.
All the same character. "aaa" returns 6 and "aaaa" returns 10: every substring is a palindrome, and a string of length n has n(n + 1)/2 substrings.
Starting j at i + 1. That skips every single-character substring and the answer comes out too small.
Counting distinct palindromes. The task counts every position separately. "aaa" has 6 palindromic substrings, not 3 distinct ones.
Non-ASCII text. Because the code works on bytes, multi-byte characters give wrong counts, as shown above.

Testing

"abbcbc" gives 9.
"" gives 0.
"a" gives 1.
"abc" gives 3.
"aaa" gives 6.
"aaaa" gives 10.

Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free