查找两个大小写字母中都存在的最大英文字母

问题陈述

给定一个由英文字母组成的字符串 s。您的任务是找到并返回字符串中同时以小写和大写形式出现的英文字母。如果不存在这样的字母，则返回一个空字符串。

使用 HashSet 的 Java 实现

输出

"R"
 ""

问题解释

• 这里的问题是找到给定字符串 s 中同时存在大小写形式的最大英文字母。需要识别唯一字符，然后循环遍历大写字母，直到找到具有两种大小写的最大字母。

函数说明

• GreatestLetter 函数包含一个 HashSet，其中包含输入字符串中的不同字符。然后它会遍历所有大写字母，以确定它们是否同时存在于集合中的相应小写字母。第一个找到的此类对的大写字母。

时间复杂度

• 填充 HashSet（第一次循环）：在这种情况下，第一次循环遍历字符串中的每个字符，平均运行时间为 O(N)，其中 N 是字符串的大小。
• 检查大写字母（第二次循环）：其次，第二次循环仅遍历一组特定的字母，从而产生恒定的时间算法。
• 对输入字符串的主要迭代的时间复杂度为 O(N)，因此，总时间复杂度为 O(N)。

空间复杂度

• 主要是，空间复杂度取决于用于存储唯一字符的 HashSet。
• HashSet 存储：在最坏的情况下，当每个字符都只作为一个成员出现在集合中时，最坏情况下的空间复杂度为 O(N)。
• 大写字母：第二次循环中的大写字母数量恒定，决定了 O(1) 的空间复杂度。

使用计数数组方法

输出

"R"
""

说明

函数说明

• Greatest Letter 函数用于查找给定字符串 's' 中同时存在大小写形式的最大英文字母。通过两个数组 'up' 和 'low' 来检查这些字母的大小写形式。该函数处理字符串并将字母存储在数组中。
• 然后，它会遍历所有数组以查找在两种可能性中都出现的最高字母。

时间复杂度

• 数组填充（第一次循环）：第一次循环遍历输入字符串的每个字符，并检查它是大写字符还是小写字符，并更新相应的数组。因此，对于长度为 N 的字符串，这会产生 O(N) 的时间复杂度。
• 数组比较（第二次循环）：在这种情况下，第二次循环遍历一个包含二十六个元素的数组，并检查任何一种情况下的字母。因此，这提供了连续的时间性能。
• 总时间复杂度为 O(N)。因此，对输入字符串的主要线性迭代占主导地位。

空间复杂度

• 大写和小写数组：两个数组（up 和 low）共包含 26 个元素，表示给定的字母是否被视为大写或小写。因此，每个数组的空间复杂度为 O(1)，整个程序的空间复杂度为 O(1)。
• 其他变量：其他变量，如 ans 和循环计数器，需要恒定的空间，并且独立于输入的大小。