Calculate time required to type a word using given single-row keyboard
Given a string keyboardLayout of size 26 representing the sequence of characters present in a single row of a keyboard and a string word, the task is to calculate the total time taken to type the word, starting from the 0th key, if moving to adjacent keys requires unit time.
Examples:
Input: keyboardLayout = “abcdefghijklmnopqrstuvwxyz”, word = “dog”
Output: 22
Explanation:
Pressing the key ‘d’ requires 3 units of time ( i.e. ‘a’ -> ‘b’ -> ‘c’ -> ‘d’)
Pressing the key ‘o’ requires 11 units of time ( i.e. ‘d’ -> ‘e’ -> ‘f’ -> ‘g’ -> ‘h’ -> ‘i’ -> ‘j’ -> ‘k’ -> ‘l’ -> ‘m’ -> ‘n’ -> ‘o’)
Pressing the key ‘g’ requires 8 units of time ( i.e. ‘o’ -> ‘n’ -> ‘m’ -> ‘l’ -> ‘k’ -> ‘j’ -> ‘i’ -> ‘h’ -> ‘g’)
Therefore, the total time taken = 3 + 11 + 8 = 22.Input: keyboardLayout = “abcdefghijklmnopqrstuvwxyz”, word = “abcdefghijklmnopqrstuvwxyz”
Output: 25
Approach: Follow the steps below to solve the problem:
- Initialize a vector, say pos, to store the position of all the characters.
- Initialize two variables, say last, to store the last updated index, and result, to store the total time taken to type the word.
- Iterate over the characters of the string word:
- Initialize two variables, say destination, to store the index of the next character required to be typed, and distance, to store the distance of that index from the current index.
- Add the value of distance to result.
- Update the last to destination.
- After completing the above operations, print the value of result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate time// taken to type the given wordint timeTakenToType(string& keyboardLayout, string& word){ // Stores position of characters vector<int> pos(26); // Iterate over the range [0, 26] for (int i = 0; i < 26; ++i) { // Set position of each character char ch = keyboardLayout[i]; pos[ch - 'a'] = i; } // Store the last index int last = 0; // Stores the total time taken int result = 0; // Iterate over the characters of word for (int i = 0; i < (int)word.size(); ++i) { char ch = word[i]; // Stores index of the next character int destination = pos[ch - 'a']; // Stores the distance of current // character from the next character int distance = abs(destination - last); // Update the result result += distance; // Update last position last = destination; } // Print the result cout << result;}// Driver Codeint main(){ // Given keyboard layout string keyboardLayout = "acdbefghijlkmnopqrtsuwvxyz"; // Given word string word = "dog"; // Function call to find the minimum // time required to type the word timeTakenToType(keyboardLayout, word); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to calculate time // taken to type the given word static void timeTakenToType(String keyboardLayout, String word) { // Stores position of characters int[] pos = new int[26]; // Iterate over the range [0, 26] for (int i = 0; i < 26; i++) { // Set position of each character char ch = keyboardLayout.charAt(i); pos[ch - 'a'] = i; } // Store the last index int last = 0; // Stores the total time taken int result = 0; // Iterate over the characters of word for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); // Stores index of the next character int destination = pos[ch - 'a']; // Stores the distance of current // character from the next character int distance = Math.abs(destination - last); // Update the result result += distance; // Update last position last = destination; } System.out.println(result); } // Driver Code public static void main(String[] args) { // Given keyboard layout String keyboardLayout = "acdbefghijlkmnopqrtsuwvxyz"; // Given word String word = "dog"; // Function call to find the minimum // time required to type the word timeTakenToType(keyboardLayout, word); }}// This code is contributed by aadityapburujwale. |
Python3
# Python3 program for the above approach# Function to calculate time# taken to type the given worddef timeTakenToType(keyboardLayout, word): # Stores position of characters pos = [0]*(26) # Iterate over the range [0, 26] for i in range(26): # Set position of each character ch = keyboardLayout[i] pos[ord(ch) - ord('a')] = i # Store the last index last = 0 # Stores the total time taken result = 0 # Iterate over the characters of word for i in range(len(word)): ch = word[i] # Stores index of the next character destination = pos[ord(ch) - ord('a')] # Stores the distance of current # character from the next character distance = abs(destination - last) # Update the result result += distance # Update last position last = destination # Print result print (result)# Driver Codeif __name__ == '__main__': # Given keyboard layout keyboardLayout = "acdbefghijlkmnopqrtsuwvxyz" # Given word word = "dog" # Function call to find the minimum # time required to type the word timeTakenToType(keyboardLayout, word) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;public class GFG { // Function to calculate time // taken to type the given word static void timeTakenToType(String keyboardLayout, String word) { // Stores position of characters int[] pos = new int[26]; // Iterate over the range [0, 26] for (int i = 0; i < 26; i++) { // Set position of each character char ch = keyboardLayout[i]; pos[ch - 'a'] = i; } // Store the last index int last = 0; // Stores the total time taken int result = 0; // Iterate over the characters of word for (int i = 0; i < word.Length; i++) { char ch = word[i]; // Stores index of the next character int destination = pos[ch - 'a']; // Stores the distance of current // character from the next character int distance = Math.Abs(destination - last); // Update the result result += distance; // Update last position last = destination; } Console.WriteLine(result); } // Driver Code public static void Main(String[] args) { // Given keyboard layout String keyboardLayout = "acdbefghijlkmnopqrtsuwvxyz"; // Given word String word = "dog"; // Function call to find the minimum // time required to type the word timeTakenToType(keyboardLayout, word); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program for the above approach// Function to calculate time// taken to type the given wordfunction timeTakenToType(keyboardLayout, word){ // Stores position of characters var pos = Array(26).fill(0); // Iterate over the range [0, 26] for(var i = 0; i < 26; ++i) { // Set position of each character var ch = keyboardLayout[i]; pos[ch.charCodeAt(0) - 'a'.charCodeAt(0)] = i; } // Store the last index var last = 0; // Stores the total time taken var result = 0; // Iterate over the characters of word for(var i = 0; i < word.length; ++i) { var ch = word[i]; // Stores index of the next character var destination = pos[ch.charCodeAt(0) - 'a'.charCodeAt(0)]; // Stores the distance of current // character from the next character var distance = Math.abs(destination - last); // Update the result result += distance; // Update last position last = destination; } // Print the result document.write(result);}// Driver Code// Given keyboard layoutvar keyboardLayout = "acdbefghijlkmnopqrtsuwvxyz";// Given wordvar word = "dog";// Function call to find the minimum// time required to type the wordtimeTakenToType(keyboardLayout, word);// This code is contributed by rutvik_56</script> |
Output
22
Time Complexity: O(N), where N is the size of the string word.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
