Question

2309. Greatest English Letter in Upper and Lower Case

中文文档

Description

Given a string of English letters s, return _the greatest English letter which occurs as both a lowercase and uppercase letter in_ s. The returned letter should be in uppercase. If no such letter exists, return _an empty string_.

An English letter b is greater than another letter a if b appears after a in the English alphabet.

 

Example 1:

Input: s = "lEeTcOdE"
Output: "E"
Explanation:
The letter 'E' is the only letter to appear in both lower and upper case.

Example 2:

Input: s = "arRAzFif"
Output: "R"
Explanation:
The letter 'R' is the greatest letter to appear in both lower and upper case.
Note that 'A' and 'F' also appear in both lower and upper case, but 'R' is greater than 'F' or 'A'.

Example 3:

Input: s = "AbCdEfGhIjK"
Output: ""
Explanation:
There is no letter that appears in both lower and upper case.

 

Constraints:

• 1 <= s.length <= 1000
• s consists of lowercase and uppercase English letters.

Solutions

Solution 1: Hash Table + Enumeration

First, we use a hash table $ss$ to record all the letters that appear in the string $s$. Then we start enumerating from the last letter of the uppercase alphabet. If both the uppercase and lowercase forms of the current letter are in $ss$, we return that letter.

At the end of the enumeration, if no letter that meets the conditions is found, we return an empty string.

The time complexity is $O(n)$, and the space complexity is $O(C)$. Here, $n$ and $C$ are the length of the string $s$ and the size of the character set, respectively.

class Solution:
  def greatestLetter(self, s: str) -> str:
    ss = set(s)
    for c in ascii_uppercase[::-1]:
      if c in ss and c.lower() in ss:
        return c
    return ''

class Solution {
  public String greatestLetter(String s) {
    Set<Character> ss = new HashSet<>();
    for (char c : s.toCharArray()) {
      ss.add(c);
    }
    for (char a = 'Z'; a >= 'A'; --a) {
      if (ss.contains(a) && ss.contains((char) (a + 32))) {
        return String.valueOf(a);
      }
    }
    return "";
  }
}

class Solution {
public:
  string greatestLetter(string s) {
    unordered_set<char> ss(s.begin(), s.end());
    for (char c = 'Z'; c >= 'A'; --c) {
      if (ss.count(c) && ss.count(char(c + 32))) {
        return string(1, c);
      }
    }
    return "";
  }
};

func greatestLetter(s string) string {
  ss := map[rune]bool{}
  for _, c := range s {
    ss[c] = true
  }
  for c := 'Z'; c >= 'A'; c-- {
    if ss[c] && ss[rune(c+32)] {
      return string(c)
    }
  }
  return ""
}

function greatestLetter(s: string): string {
  const ss = new Array(128).fill(false);
  for (const c of s) {
    ss[c.charCodeAt(0)] = true;
  }
  for (let i = 90; i >= 65; --i) {
    if (ss[i] && ss[i + 32]) {
      return String.fromCharCode(i);
    }
  }
  return '';
}

impl Solution {
  pub fn greatest_letter(s: String) -> String {
    let mut arr = [0; 26];
    for &c in s.as_bytes().iter() {
      if c >= b'a' {
        arr[(c - b'a') as usize] |= 1;
      } else {
        arr[(c - b'A') as usize] |= 2;
      }
    }
    for i in (0..26).rev() {
      if arr[i] == 3 {
        return char::from(b'A' + (i as u8)).to_string();
      }
    }
    "".to_string()
  }
}

/**
 * @param {string} s
 * @return {string}
 */
var greatestLetter = function (s) {
  const ss = new Array(128).fill(false);
  for (const c of s) {
    ss[c.charCodeAt(0)] = true;
  }
  for (let i = 90; i >= 65; --i) {
    if (ss[i] && ss[i + 32]) {
      return String.fromCharCode(i);
    }
  }
  return '';
};

Solution 2: Bit Manipulation (Space Optimization)

We can use two integers $mask1$ and $mask2$ to record the lowercase and uppercase letters that appear in the string $s$, respectively. The $i$-th bit of $mask1$ indicates whether the $i$-th lowercase letter appears, and the $i$-th bit of $mask2$ indicates whether the $i$-th uppercase letter appears.

Then we perform a bitwise AND operation on $mask1$ and $mask2$. The $i$-th bit of the resulting $mask$ indicates whether the $i$-th letter appears in both uppercase and lowercase.

Next, we just need to get the position of the highest $1$ in the binary representation of $mask$, and convert it to the corresponding uppercase letter. If all binary bits are not $1$, it means that there is no letter that appears in both uppercase and lowercase, so we return an empty string.

The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.

class Solution:
  def greatestLetter(self, s: str) -> str:
    mask1 = mask2 = 0
    for c in s:
      if c.islower():
        mask1 |= 1 << (ord(c) - ord("a"))
      else:
        mask2 |= 1 << (ord(c) - ord("A"))
    mask = mask1 & mask2
    return chr(mask.bit_length() - 1 + ord("A")) if mask else ""

class Solution {
  public String greatestLetter(String s) {
    int mask1 = 0, mask2 = 0;
    for (int i = 0; i < s.length(); ++i) {
      char c = s.charAt(i);
      if (Character.isLowerCase(c)) {
        mask1 |= 1 << (c - 'a');
      } else {
        mask2 |= 1 << (c - 'A');
      }
    }
    int mask = mask1 & mask2;
    return mask > 0 ? String.valueOf((char) (31 - Integer.numberOfLeadingZeros(mask) + 'A'))
            : "";
  }
}

class Solution {
public:
  string greatestLetter(string s) {
    int mask1 = 0, mask2 = 0;
    for (char& c : s) {
      if (islower(c)) {
        mask1 |= 1 << (c - 'a');
      } else {
        mask2 |= 1 << (c - 'A');
      }
    }
    int mask = mask1 & mask2;
    return mask ? string(1, 31 - __builtin_clz(mask) + 'A') : "";
  }
};

func greatestLetter(s string) string {
  mask1, mask2 := 0, 0
  for _, c := range s {
    if unicode.IsLower(c) {
      mask1 |= 1 << (c - 'a')
    } else {
      mask2 |= 1 << (c - 'A')
    }
  }
  mask := mask1 & mask2
  if mask == 0 {
    return ""
  }
  return string(byte(bits.Len(uint(mask))-1) + 'A')
}