✅ C++ | No extra Space O(1) | Simple Solution with Explanation
Intuition\nLet\'s assume that s = "arRAzFif". Sorting the string in descending order will result in s = "zrifaRFA". Now, let\'s see which small letters are pres
# Intuition\nLet\'s assume that `s = "arRAzFif"`. Sorting the string in descending order will result in `s = "zrifaRFA"`. Now, let\'s see which small letters are present in the string and increment their occurrence by 1. Moving to the upper-case letters, iterate through them returning the first character with a lower-case counterpart using a vector of size 26.\n\n# Approach\n1. Sort the string in descending order so that the first segment is lowercase letters.\n2. Use `lowerChars` to count the frequency of lower cased letters.\n3. Iterate and increment frequency till the current index is an upper-case letter.\n4. Iterate through upper-case letters and check if there is a lower-case letter presented in the string.\n5. Return an empty string if there is no letter satisfying such case;\n\n\n# Complexity\n- Time complexity: $$O(n)$$, Linear, two pass considering the sorting function.\n- Space complexity: $$O(1)$$, since there is only a fixed size vector.\n\n# Code\n```\nclass Solution {\npublic:\n    string greatestLetter(string s) {\n        sort(s.begin(), s.end(), greater<char>());\n        vector<int> lowerChars(26, 0);\n        int i = 0, n = s.size();\n        while(i < n && islower(s[i])) {\n            ++lowerChars[s[i] - \'a\'];\n            ++i;\n        }\n        while(i < n && isupper(s[i])) {\n            if(lowerChars[s[i] - \'A\'] > 0)\n                return string(1, s[i]);\n            ++i;\n        }\n        return "";\n    }\n};\n```
['Array', 'Hash Table', 'String', 'C++']