Taro Logo

Single-Row Keyboard

#1688 Most AskedEasy
31 views
Topics:
ArraysStrings

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|.

Return the total time to type the string word.

Example 1:

Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
Output: 4
Explanation: The index moves from 0 to 2 to write 'c' then from 2 to 1 to write 'b' then from 1 to 0 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 contains English lowercase letters only.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Is the keyboard string guaranteed to contain each letter of the alphabet exactly once?
  2. Is the `word` string guaranteed to only contain letters present in the `keyboard` string?
  3. Can the `keyboard` or `word` strings be empty or null?
  4. Is case sensitivity a factor? Should I treat uppercase and lowercase letters differently?
  5. If the same character appears multiple times in `word`, should I calculate the distance from the previous occurrence or the first occurrence on the keyboard?

Brute Force Solution

Approach

The brute force approach to this keyboard problem involves trying every possible character-by-character path to spell out the target word. We essentially simulate using the keyboard in every conceivable way to find the fastest way to type the word. We then choose the fastest one.

Here's how the algorithm would work step-by-step:

  1. Start at the beginning of the target word.
  2. For the first letter, find its position on the keyboard.
  3. For the second letter, calculate the distance from the first letter to the second letter on the keyboard.
  4. Do this for every letter in the target word: find the distance to the next letter.
  5. Keep track of the total distance of this one complete path.
  6. Repeat the above process for every possible path by exploring different routes at each letter.
  7. Compare the total distances of all the paths.
  8. The path with the shortest total distance is the fastest way to type the word.

Code Implementation

def single_row_keyboard_brute_force(keyboard, word):
    keyboard_length = len(keyboard)
    word_length = len(word)
    minimum_distance = float('inf')

    def calculate_distance(current_index, word_index, current_distance):
        nonlocal minimum_distance
        
        # If we've reached the end of the word, update the minimum distance
        if word_index == word_length:
            minimum_distance = min(minimum_distance, current_distance)
            return

        target_character = word[word_index]
        
        # Find the index of the target character on the keyboard
        target_index = keyboard.find(target_character)

        distance = abs(current_index - target_index)
        
        # Recursively calculate the distance for the next character in the word
        calculate_distance(target_index, word_index + 1, current_distance + distance)

    # The starting position is always index 0 on the keyboard
    calculate_distance(0, 0, 0)

    return minimum_distance

Big(O) Analysis

Time Complexity
O(m^n) – The algorithm explores every possible path to type the word of length n. At each character in the word, it potentially has to consider all m positions on the keyboard to find the next character. This branching factor of m repeats for each of the n characters in the word, leading to a time complexity of O(m^n), where m is the length of the keyboard and n is the length of the target word. This represents an exponential growth in computation.
Space Complexity
O(N^L) – The brute force approach explores every possible path to spell the target word. Because the algorithm explores all possible routes at each letter, and since we're not given a constraint that states that characters can only be used once or anything else, we can say that at each point, there are 'N' possible choices. The depth of this recursion or the length of each 'path' is 'L', where L is the length of the target word. Therefore, the space complexity comes from tracking the currently explored path, which can have a maximum depth of L. However, since at each step we are considering all possible positions (N, the length of the keyboard row), the space complexity can be calculated as the size of the tree that we are exploring which is O(N^L), where N is the size of the keyboard and L is the length of the target word. The recursion stack could grow proportionally to N^L in the worst-case scenario.

Optimal Solution

Approach

The goal is to find the total distance a finger needs to travel on a single-row keyboard to type a given word. The key is to quickly figure out where each letter is located on the keyboard and then calculate the distance between each consecutive letter.

Here's how the algorithm would work step-by-step:

  1. First, create a quick way to look up the position of each letter on the keyboard. For example, you could remember where each letter is or write it down in a table.
  2. Start at the first letter of the word you want to type. Find its position on the keyboard.
  3. Move to the next letter in the word. Find its position on the keyboard.
  4. Calculate the distance between these two letter positions. The distance is simply the difference between the two positions (always make sure it's a positive number).
  5. Add this distance to the total distance traveled.
  6. Repeat steps 3-5 for all the remaining letters in the word, always calculating the distance from the current letter to the next one and adding it to the total.
  7. The final total distance is the answer.

Code Implementation

def calculate_keyboard_distance(keyboard_layout, word_to_type):
    keyboard_position_map = {}
    for index, character in enumerate(keyboard_layout): 
        keyboard_position_map[character] = index

    total_distance_traveled = 0
    
    # Initialize the starting position to the first character in the word
    current_position = keyboard_position_map[word_to_type[0]]

    # Iterate through the rest of the word to calculate distance
    for i in range(1, len(word_to_type)):
        next_character = word_to_type[i]
        next_position = keyboard_position_map[next_character]
        
        # Calculate the absolute distance between positions
        distance = abs(next_position - current_position)
        
        total_distance_traveled += distance

        # Update the current position for the next iteration
        current_position = next_position

    return total_distance_traveled

Big(O) Analysis

Time Complexity
O(n) – The algorithm iterates through the word (of length n) once. Inside the loop, a constant-time lookup (using a dictionary or similar structure established at the beginning) is performed to find the position of each character on the keyboard. The distance calculation is also constant time. Therefore, the dominant factor is the single loop iterating through the word, making the time complexity O(n).
Space Complexity
O(1) – The provided solution uses a lookup table to store the position of each character on the keyboard. The size of this lookup table is fixed and independent of the length of the word to be typed. No other data structures such as arrays, lists, or hashmaps are created that scale with the input word's length. Therefore, the space complexity is constant, regardless of the word's length (N).

Edge Cases

Empty keyboard string
How to Handle:
Return 0 immediately since no characters can be found.
Null keyboard or word string
How to Handle:
Throw IllegalArgumentException to signal invalid input.
Keyboard string length 1
How to Handle:
If the target word has length 1, return 0, else return Integer.MAX_VALUE or throw an exception, based on problem requirement.
Word string contains characters not in keyboard
How to Handle:
Handle missing characters by returning Integer.MAX_VALUE when character location is missing in the map.
Word string is very long (potential performance issue)
How to Handle:
HashMap lookup provides O(1) access, making time complexity linearly proportional to the word's length.
Keyboard string contains duplicate characters.
How to Handle:
The last occurrence of duplicate characters in keyboard overwrites the previous index in hashmap, using the correct character index.
Word string is empty
How to Handle:
Return 0 since no movement is required.
Integer overflow if the word is extremely long, and characters are far apart in keyboard layout
How to Handle:
Use long to store the distance to prevent integer overflow, and cast back to int if needed and appropriate, handling the overflow if the distance exceeds Integer.MAX_VALUE.
0/1916 completed