Skip to content

744. Find Smallest Letter Greater Than Target

Difficulty Topics

Description

You are given an array of characters letters that is sorted in non-decreasing order, and a character target. There are at least two different characters in letters.

Return the smallest character in letters that is lexicographically greater than target. If such a character does not exist, return the first character in letters.

 

Example 1:

Input: letters = ["c","f","j"], target = "a"
Output: "c"
Explanation: The smallest character that is lexicogrpahically greater than 'a' in letters is 'c'.

Example 2:

Input: letters = ["c","f","j"], target = "c"
Output: "f"
Explanation: The smallest character that is lexicogrpahically greater than 'c' in letters is 'f'.

Example 3:

Input: letters = ["x","x","y","y"], target = "z"
Output: "x"
Explanation: There are no characters in letters that is lexicographically greater than 'z' so we return letters[0].

 

Constraints:

  • 2 <= letters.length <= 104
  • letters[i] is a lowercase English letter.
  • letters is sorted in non-decreasing order.
  • letters contains at least two different characters.
  • target is a lowercase English letter.

Solution

find-smallest-letter-greater-than-target.py
class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        count = [0] * 26

        for x in letters:
            index = ord(x) - ord("a")
            count[index] += 1

        index = ord(target) - ord("a") + 1

        for i in range(26):
            if count[(index + i) % 26] > 0:
                return chr(ord("a") + (index + i) % 26)