Teaching Kids Programming – Two Pointer Algorithm to Capitalize the Title String

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a string title consisting of one or more words separated by a single space, where each word consists of English letters. Capitalize the string by changing the capitalization of each word such that:

If the length of the word is 1 or 2 letters, change all letters to lowercase. Otherwise, change the first letter to uppercase and the remaining letters to lowercase. Return the capitalized title.

Example 1:
Input: title = “capiTalIze tHe titLe”
Output: “Capitalize The Title”
Explanation:
Since all the words have a length of at least 3, the first letter of each word is uppercase, and the remaining letters are lowercase.

Example 2:
Input: title = “First leTTeR of EACH Word”
Output: “First Letter of Each Word”
Explanation:
The word “of” has length 2, so it is all lowercase.
The remaining words have a length of at least 3, so the first letter of each remaining word is uppercase, and the remaining letters are lowercase.

Example 3:
Input: title = “i lOve leetcode”
Output: “i Love Leetcode”
Explanation:
The word “i” has length 1, so it is lowercase.
The remaining words have a length of at least 3, so the first letter of each remaining word is uppercase, and the remaining letters are lowercase.

Constraints:
1 <= title.length <= 100
title consists of words separated by a single space without any leading or trailing spaces.
Each word consists of uppercase and lowercase English letters and is non-empty.

Hints:
Firstly, try to find all the words present in the string.
On the basis of each word’s lengths, simulate the process explained in Problem.

Capitalize the Title String via Join and Split

We first break the string into words by using the string split function. Then we go through each word and make first letter uppercase if necessary. We can use the enumerate function to give us the index and the word string tuple pair.

1
2
3
4
5
6
7
8
9

class Solution:
    def capitalizeTitle(self, title: str) -> str:
        s = title.split()
        for i in range(len(s)):
            if len(s[i]) <= 2:
                s[i] = s[i].lower()
            else:
                s[i] = s[i][0].upper() + s[i][1:].lower()
        return " ".join(s)

class Solution:
    def capitalizeTitle(self, title: str) -> str:
        s = title.split()
        for i in range(len(s)):
            if len(s[i]) <= 2:
                s[i] = s[i].lower()
            else:
                s[i] = s[i][0].upper() + s[i][1:].lower()
        return " ".join(s)

To make a word only the first letter uppercase, we can also use the inbuilt title() function.

Two Pointer Algorithm to Capitalize the Title String

The Two Pointer Algorithm applies here. The first pointer tracks the begining of each word, and the second pointer moves character by character. When we meet a word bounary either a space of beyond the end, we need to make first character uppercase if the length is larger than two. Also, we have to make all letters along the way lowercase.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def capitalizeTitle(self, title: str) -> str:
        i = j = 0
        s = list(title)
        n = len(s)        
        while i <= n:
            if i == n or s[i] == ' ':
                if i - j > 2:
                    s[j] = s[j].upper()
                j = i + 1
            else:
                s[i] = s[i].lower()
            i += 1
        return "".join(s)

class Solution:
    def capitalizeTitle(self, title: str) -> str:
        i = j = 0
        s = list(title)
        n = len(s)        
        while i <= n:
            if i == n or s[i] == ' ':
                if i - j > 2:
                    s[j] = s[j].upper()
                j = i + 1
            else:
                s[i] = s[i].lower()
            i += 1
        return "".join(s)

Both algorithms are performing at O(N) time and space (complexity). The string in Python is immutable and thus we have to convert it to list of strings.

–EOF (The Ultimate Computing & Technology Blog) —