Welcome to Subscribe On Youtube

3846. Total Distance to Type a String Using One Finger 🔒

Description

There is a special keyboard where keys are arranged in a rectangular grid as follows.

q	w	e	r	t	y	u	i	o	p
a	s	d	f	g	h	j	k	l
z	x	c	v	b	n	m

You are given a string s that consists of lowercase English letters only. Return an integer denoting the total distance to type s using only one finger. Your finger starts on the key 'a'.

The distance between two keys at (r1, c1) and (r2, c2) is \|r1 - r2\| + \|c1 - c2\|.

 

Example 1:

Input: s = "hello"

Output: 17

Explanation:

• Your finger starts at 'a', which is at (1, 0).
• Move to 'h', which is at (1, 5). The distance is \|1 - 1\| + \|0 - 5\| = 5.
• Move to 'e', which is at (0, 2). The distance is \|1 - 0\| + \|5 - 2\| = 4.
• Move to 'l', which is at (1, 8). The distance is \|0 - 1\| + \|2 - 8\| = 7.
• Move to 'l', which is at (1, 8). The distance is \|1 - 1\| + \|8 - 8\| = 0.
• Move to 'o', which is at (0, 8). The distance is \|1 - 0\| + \|8 - 8\| = 1.
• Total distance is 5 + 4 + 7 + 0 + 1 = 17.

Example 2:

Input: s = "a"

Output: 0

Explanation:

• Your finger starts at 'a', which is at (1, 0).
• Move to 'a', which is at (1, 0). The distance is \|1 - 1\| + \|0 - 0\| = 0.
• Total distance is 0.

 

Constraints:

• 1 <= s.length <= 104
• s consists of lowercase English letters only.

Solutions

Solution 1: Simulation

We define a hash table $\textit{pos}$ to store the position of each character on the keyboard. For each character in string $s$, we calculate the distance from the previous character to the current character and accumulate it to the answer. Finally, we return the answer.

The time complexity is $O(n)$, where $n$ is the length of string $s$. The space complexity is $O(|\Sigma|)$, where $\Sigma$ is the character set, which here is 26 lowercase English letters.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      private static final Map<Character, int[]> pos = new HashMap<>();
  
      static {
          String[] keys = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
          for (int i = 0; i < keys.length; i++) {
              for (int j = 0; j < keys[i].length(); j++) {
                  pos.put(keys[i].charAt(j), new int[] {i, j});
              }
          }
      }
  
      public int totalDistance(String s) {
          char pre = 'a';
          int ans = 0;
  
          for (char cur : s.toCharArray()) {
              int[] p1 = pos.get(pre);
              int[] p2 = pos.get(cur);
              ans += Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
              pre = cur;
          }
  
          return ans;
      }
  }
  

• class Solution {
  public:
      int totalDistance(string s) {
          static unordered_map<char, pair<int, int>> pos = [] {
              unordered_map<char, pair<int, int>> m;
              vector<string> keys = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
              for (int i = 0; i < keys.size(); ++i) {
                  for (int j = 0; j < keys[i].size(); ++j) {
                      m[keys[i][j]] = {i, j};
                  }
              }
              return m;
          }();
  
          char pre = 'a';
          int ans = 0;
  
          for (char cur : s) {
              auto [x1, y1] = pos[pre];
              auto [x2, y2] = pos[cur];
              ans += abs(x1 - x2) + abs(y1 - y2);
              pre = cur;
          }
  
          return ans;
      }
  };
  

• pos = {}
  keys = ['qwertyuiop', 'asdfghjkl', 'zxcvbnm']
  for i, row in enumerate(keys):
      for j, key in enumerate(row):
          pos[key] = (i, j)
  
  
  class Solution:
      def totalDistance(self, s: str) -> int:
          pre = 'a'
          ans = 0
          for cur in s:
              x1, y1 = pos[pre]
              x2, y2 = pos[cur]
              dist = abs(x1 - x2) + abs(y1 - y2)
              ans += dist
              pre = cur
          return ans
  
  

• var pos map[byte][2]int
  
  func init() {
  	pos = make(map[byte][2]int)
  	keys := []string{"qwertyuiop", "asdfghjkl", "zxcvbnm"}
  	for i, row := range keys {
  		for j := 0; j < len(row); j++ {
  			pos[row[j]] = [2]int{i, j}
  		}
  	}
  }
  
  func totalDistance(s string) int {
  	pre := byte('a')
  	ans := 0
  
  	for i := 0; i < len(s); i++ {
  		cur := s[i]
  		p1 := pos[pre]
  		p2 := pos[cur]
  		ans += abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
  		pre = cur
  	}
  
  	return ans
  }
  
  func abs(x int) int {
  	if x < 0 {
  		return -x
  	}
  	return x
  }
  

• const pos: Record<string, [number, number]> = {};
  
  const keys = ['qwertyuiop', 'asdfghjkl', 'zxcvbnm'];
  keys.forEach((row, i) => {
      [...row].forEach((key, j) => {
          pos[key] = [i, j];
      });
  });
  
  function totalDistance(s: string): number {
      let pre = 'a';
      let ans = 0;
  
      for (const cur of s) {
          const [x1, y1] = pos[pre];
          const [x2, y2] = pos[cur];
          ans += Math.abs(x1 - x2) + Math.abs(y1 - y2);
          pre = cur;
      }
  
      return ans;
  }
  
  

All Problems

All Solutions