algoadvance

Leetcode 1974. Minimum Time to Type Word Using Special Typewriter

Problem Statement

LeetCode problem 1974: “Minimum Time to Type Word Using Special Typewriter”

There is a special typewriter with a single row of 26 lowercase English letters from ‘a’ to ‘z’. Initially, the pointer is at the letter ‘a’. The typewriter has two special functions:

1. Move the pointer to the right or left by one slot.
2. Type the character it is currently at.

Given a string word, return the minimum time to type the entire string. The time to move one slot to the left or right is 1, and the time to type a character is also 1.

Clarifying Questions

1. Case Sensitivity: Should we consider both lowercase and uppercase letters?
   • No, only lowercase letters are involved in this problem.
2. Input Constraints: What are the constraints on the length of word?
   • 1 <= word.length <= 100.
3. Allowed Operations: Can we move the pointer in both directions and how are the movements counted?
   • Yes, we can move the pointer both left and right. The time for each movement is counted as 1.

Strategy

• Start from the initial position ‘a’.
• For each character in word, calculate the shortest distance the pointer must move to reach the target character.
• We can move clockwise or counterclockwise, so we should take the minimum of these two distances.
• Sum up all the move times and add the time taken to type each character (which is equal to the length of the word since each character typing takes 1 unit of time).

Code

#include <iostream>
#include <string>
#include <algorithm>

int minTimeToType(std::string word) {
    int totalTime = 0;
    char currentPos = 'a';

    for (char c : word) {
        int clockwiseDist = abs(c - currentPos);
        int counterClockwiseDist = 26 - clockwiseDist;
        totalTime += std::min(clockwiseDist, counterClockwiseDist) + 1;
        currentPos = c;
    }

    return totalTime;
}

int main() {
    std::string word = "cba";
    std::cout << "Minimum time to type word \"" << word << "\": " << minTimeToType(word) << " units." << std::endl;
    return 0;
}

Time Complexity

• Time Complexity: O(n) where n is the length of the word. We iterate through each character in the word exactly once.
• Space Complexity: O(1) since we use a fixed amount of extra space regardless of the input size.

This solution efficiently calculates the minimum time required to type the given word using a single-row typewriter by evaluating both clockwise and counterclockwise distances and selecting the minimum at each step.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?