Teaching Kids Programming – Single-Row Keyboard via Hash Table

Teaching Kids Programming: Videos on Data Structures and Algorithms

There is a special keyboard with all keys in a single row. Given a string keyboard of length 26 indicating the layout of the keyboard (indexed from 0 to 25). Initially, your finger is at index 0. To type a character, you have to move your finger to the index of the desired character. The time taken to move your finger from index i to index j is |i – j|.

You want to type a string word. Write a function to calculate how much time it takes to type it with one finger.

Example 1:
Input: keyboard = “abcdefghijklmnopqrstuvwxyz”, word = “cba”
Output: 4
Explanation: The index moves from 0 to 2 to write ‘c’ then to 1 to write ‘b’ then to 0 again to write ‘a’.
Total time = 2 + 1 + 1 = 4.

Example 2:
Input: keyboard = “pqrstuvwxyzabcdefghijklmno”, word = “leetcode”
Output: 73

Constraints:
keyboard.length == 26
keyboard contains each English lowercase letter exactly once in some order.
1 <= word.length <= 104
word[i] is an English lowercase letter.

Hints:
Can be the problem divided in parts, so solving each part and sum their solutions it should return the answer? Yes, you only need to divide the problem in finger jumps.
In each finger jump you need to move your finger from one character to another, you need to know its index.
Map each character to it’s index.
Use a hash table to do that.

Estimate Finger Move Time of Single-Row Keyboard via Hash Table

We need to look up the index for a character and this can be best done via a Hash TableTeaching Kids Programming – Using Hash Set or Hash Table to Count Next Element. Then, we follow characters to add up the time required moving between two consecutive letters.

1
2
3
4
5
6
7
8
9

class Solution:
    def calculateTime(self, keyboard: str, word: str) -> int:
        d = {}
        for i, c in enumerate(keyboard):
            d[c] = i
        ans = d[word[0]]
        for i in range(1, len(word)):
            ans += abs(d[word[i]] - d[word[i - 1]])
        return ans

class Solution:
    def calculateTime(self, keyboard: str, word: str) -> int:
        d = {}
        for i, c in enumerate(keyboard):
            d[c] = i
        ans = d[word[0]]
        for i in range(1, len(word)):
            ans += abs(d[word[i]] - d[word[i - 1]])
        return ans

We can use one-liner to construct the hash map (dictionary, mapping between characters to their indices):

1
2
3
4
5
6
7

class Solution:
    def calculateTime(self, keyboard: str, word: str) -> int:
        d = {k: i for i, k in enumerate(keyboard)}
        ans = d[word[0]]
        for i in range(1, len(word)):
            ans += abs(d[word[i]] - d[word[i - 1]])
        return ans

class Solution:
    def calculateTime(self, keyboard: str, word: str) -> int:
        d = {k: i for i, k in enumerate(keyboard)}
        ans = d[word[0]]
        for i in range(1, len(word)):
            ans += abs(d[word[i]] - d[word[i - 1]])
        return ans

The time/space complexity is O(N) where N is the number of the characters in the word. There are only 26 characters for a keyboard and thus O(26) is essentially O(1).

Single Row Keyboard Algorithms

• Go Lang Programming Exercise: Single-Row Keyboard
• Single-Row Keyboard Algorithms to Estimate the Finger Moving Time
• Teaching Kids Programming – Single-Row Keyboard via Hash Table

–EOF (The Ultimate Computing & Technology Blog) —