744.Find Smallest Letter Greater Than Target
===

###### tags: `Easy`,`Array`,`Binary Search`

[744. Find Smallest Letter Greater Than Target](https://leetcode.com/problems/find-smallest-letter-greater-than-target/)

### 題目描述

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 lexicographically greater than 'a' in letters is 'c'.

**Example 2:**

Input: letters = ["c","f","j"], target = "c"
Output: "f"
Explanation: The smallest character that is lexicographically 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` <= 10^4^
* `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.

### 解答

#### C++

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        const auto ub = upper_bound(letters.begin(), letters.end(), target);
        return ub == letters.end() ? letters[0] : *ub;
    }
};

> [name=Jerry Wu][time=9 June, 2023]

#### Python

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        return letters[bisect_right(letters, target) % len(letters)]

> [name=Yen-Chi Chen][time=Fri, Jun 9, 2023]

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        return min([ch for ch in letters if ord(ch) > ord(target)], default=letters[0])

> [name=Ron Chen][time=Fri, Jun 9, 2023]

#### Java

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        for(char ch : letters) {
            if(ch - 'a' > target - 'a')
                return ch;
        }

        return letters[0];
    }
}

與 ChatGPT 來來回回改出來的

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        return new String(letters).chars()
                .filter(ch -> ch > target)
                .mapToObj(ch -> (char) ch)
                .findFirst()
                .orElse(letters[0]);
    }
}

> [name=Ron Chen][time=Fri, Jun 9, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)