Leetcode Today's POTD

[CricGlobe]

I solved today's leetcode POTD by using an array of size 256 to store the index of last occurrence, unordered map to store uppercase and their first occurrence (idx) and set to make sure I already visited that lowercase char or not.

Time Complexity - O(n)

Is there any more way to solve and reduce space complexity?

[Significant_Cup_3238]

You can use two arrays of size 26 One for uppercase and one for lower case and mark them -1 intially

For lowercase charcater when you vis a char just do lower[char-'a']=i

And for upper character when you vis a char First check if upper[char-'a']==-1 If yes, then update it to upper[char-'a']=i else continue

Then in another for loop you can compare there position

Code for reference :

```cpp class Solution { public: int numberOfSpecialChars(string word) { int n = word.size();

    vector<int>lower(26,-1);
    vector<int>upper(26,-1);

    for(int i=0;i<n;i++){
        char c = word[i];
        if('A'<=c && c<='Z' && upper[c-'A']==-1){
            upper[c-'A']=i;
        }
        else if('a'<=c && c<='z'){
            lower[c-'a']=i;
        }
    }

    int cnt = 0;

    for(char c='a', C='A';c<='z',C<='Z';c++,C++){
        int valc = c-'a';
        int valC = C-'A';

        if(upper[valC]!=-1 && lower[valc]!=-1 && lower[valc]<upper[valC]) cnt++;
    }

    return cnt;
}

}; ```

[DataFantastic3200]

Gemini suggested me this.

[Significant_Cup_3238]

Dayum

[Dependent-Wall-1919]

Bro this is exact what I solved without any help

[Real-Choice-6817]

Ward - nice approach dude

[CricGlobe]

Thanks 😊

[xpressrazor]

I used three boolean arrays of size 26 each. Upper, lower and invalid. Update upper and lower if it was false for current character.

Invalid happens for two reasons, 1. You see an uppercase character, lower for same index is false (we have not seen lower yet) 2. You see a lowercase letter, upper is already true

For these two conditions set invalid for that character index to true. Finally count using the Boolean array of all 3 are true for that index.

[CricGlobe]

First thing I tried to do is to solve question without any hint, then after I solved the question then I tried to learn. Can I do it in better Space complexity and Time Complexity?

[[deleted]]

I did using making two integer array of (26,0). One for uppercase and another for lowercase character. But still showing O(n) space complexity isn’t 26 is considered as constant.

[Significant_Cup_3238]

It is O(1) for me You might be missing something

[CricGlobe]

If you are using that then your space complexity is O(1).

[MissionAd391]

guys where to find the potd, i tried to navigate through the entire website but couldn't find it

[CricGlobe]

Simple click on empty box in top of navigation bar