LeetCode #2351 in Python and Go

LeetCode is a social programming platform that lets developers improve their problem solving skills while preparing for technical interviews. The questions and contests are organized by difficulty. They can be solved by typing into LeetCode’s online editor with your language of choice. Your solution is then ranked by runtime speed and memory usage.

In this post, we look at the First Letter to Apper Twice problem with Python and Go.

First Letter to Appear Twice

The description of the First Letter to Appear Twice problem is shown below:

Example Results

Input: s = “abccbaacz” Output: “c”

Input: s = “abcdd” Output: “d”

Constraints

• 2 <= s.length <= 100
• s consists of lowercase English letters.
• s has at least one repeated letter.

Python

The Python code used to solve this problem is similar to the solutions for LeetCode #1. For each character in the string s, we can dump letters into a dictionary, and then check if the next character in the string exists in the dictionary and if it does, we return that character.

The pseudocode for this is shown below.

create an empty dictionary

loop over each character in the string
  if the character is in dictionary
    return character
  otherwise create a dictionary element and set it to true or 1

The Python code for this would look like the following.

class Solution:
  def repeatedCharacter(self, s: str) -> str:
    my_dict = {}
    for char in s:
      if char in my_dict:
        return char
      else:
        my_dict[char] = 1

We create an empty dictionary called my_dict. Then we create a for loop to iterate over each letter in the string s. If the character exists in the dictionary, we know we have a match so we return the character. If the character doesn’t exist, we add it to the dictionary.

The runtime for this solution is about 54 ms.

A slight improvement in speed may be achieved with a set. You could also use a list or another string to store letters as you iterate over them.

The example below shows how you could use enumerate() to get the index for each letter. Then you could check if each letter exists in a slice of s up to the current iteration index.

class Solution:
  def repeatedCharacter(self, s):
      for index, char in enumerate(s):
          if char in s[:index]:
              return char

Go

We can create a Go solution with similar logic but our map will be slightly different.

When iterating a string using a for range loop in Go, the return elements are an index and a rune character. So, we must create a map of rune values that map to some other value, bool in this case. We choose a boolean so we can use it in our following if-statement.

An if-statement is used to get the rune from our map. If it exists, the rune is converted to a byte and is returned. Otherwise, we set the char key in the map to true.

The pseudocode for this will be:

create a map of runes that map to a boolean

loop over all the letters in the string s
  if the map contains the letter
    return the letter
  otherwise set the letter in the map to true

Turning this into Go code would look something like the following.

func repeatedCharacter(s string) byte {
  myMap := map[rune]bool{}
  for _, char := range s {
    if myMap[char] {
      return byte(char)
    } else {
      myMap[char] = true
    }
  }
  return 0
}

The runtime for this solution is 2 ms.

Summary

In this post, we looked at how to solve the First Letter to Appear Twice problem using Python and Go. In future lessons, we’ll explore more problem solving on the LeetCode platform with these two great languages.