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 word int 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 Code int 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 approach import 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 word def 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 Code if __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 approach using 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 word function 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 layout var keyboardLayout = "acdbefghijlkmnopqrtsuwvxyz" ; // Given word var word = "dog" ; // Function call to find the minimum // time required to type the word timeTakenToType(keyboardLayout, word); // This code is contributed by rutvik_56 </script> |
22
Time Complexity: O(N), where N is the size of the string word.
Auxiliary Space: O(1)
Contact Us