Smallest window (substring) that has both uppercase and corresponding lowercase characters

Due to the special property of string. There is only 26 uppercase letters and 26 lowercase letters.
We can loop every 26 letter j and denote the minimum length for any substrings starting from position i to find matches for uppercase and lowercase letter j be len[i][j]
Demo C++ code:

string s = "CATattac";
// if len[i] >= s.size() + 1, it denotes there is no matching
vector<vector<int>> len(s.size(), vector<int>(26, 0));
for (int i = 0; i < 26; ++i) {
    int upperPos = s.size() * 2;
    int lowerPos = s.size() * 2;
    for (int j = s.size() - 1; j >= 0; --j) {
        if (s[j] == 'A' + i) {
            upperPos = j;
        } else if (s[j] == 'a' + i) {
            lowerPos = j;
        }
        len[j][i] = max(lowerPos - j + 1, upperPos - j + 1);
    }
}

We also keep track of the count of characters.

// cnt[i][j] denotes the number of characters j in substring s[0..i-1]
// cnt[0][j] is always 0
vector<vector<int>> cnt(s.size() + 1, vector<int>(26, 0));
for (int i = 0; i < s.size(); ++i) {
    for (int j = 0; j < 26; ++j) {
        cnt[i + 1][j] = cnt[i][j];
        if (s[i] == 'A' + j || s[i] == 'a' + j) {
            ++cnt[i + 1][j];
        }
    }
}

Then we can loop over s.

int m = s.size() + 1;
for (int i = 0; i < s.size(); ++i) {
    bool done = false;
    int minLen = 1;
    while (!done && i + minLen <= s.size()) {
        // execute at most 26 times, a new character must be added to change minLen
        int prevMinLen = minLen;
        done = true;
        for (int j = 0; j < 26 && i + minLen <= s.size(); ++j) {
            if (cnt[i + minLen][j] - cnt[i][j] > 0) {
                // character j exists in the substring, have to find pair of it
                minLen = max(minLen, len[i][j]);
            }
        }
        if (prevMinLen != minLen) done = false;
    }
    // find overall minLen
    if (i + minLen <= s.size())
        m = min(m, minLen);
    cout << minLen << '\n';
}

Output: (if i + minLen <= s.size(), it is valid. Otherwise substring doesn't exist if starting at that position)
The invalid output difference is due to how the array len is generated.

8
4
15
14
13
12
11
10

I'm not sure whether there is a simpler solution but it is the best I could think of right now. Time complexity: O(N) with a constant of 26 * 26

Edit: I previously had O(nlog(n)) due to a unnecessary binary search.

I thought of a solution, which is technically O(n), where n is the length of the string, but the constant is pretty large.

For simplicity's sake, let's consider an analogous situation with only two letters, A and B (and their lowercase counterparts), and let l be the size of the alphabet for future reference. I worked on an example string ABabBaaA.

We start by computing the prefix counts of the number of occurrences of each letter. In this case, we get

i: 0, 1, 2, 3, 4, 5, 6, 7, 8
----------------------------
A: 0, 1, 1, 1, 1, 1, 1, 1, 2
a: 0, 0, 0, 1, 1, 1, 2, 3, 3
B: 0, 0, 1, 1, 1, 2, 2, 2, 2
b: 0, 0, 0, 0, 1, 1, 1, 1, 1

This way, assuming we are indexing the string starting from 1 (for implementation's sake you can add an extra character to the beginning, like a dollar sign $), we can get the number of occurrences of each letter on any substring in constant time (or rather -- in O(l), but in my case l is set to 2 and in your case l = 26 so technically this is constant time).

OK now we prepare arrays / vectors / queues of character indices, so if the character A appears on indices 1 and 8, the structure will consist of 1 and 8. We get

A: 1, 8
a: 3, 6, 7
B: 2, 5
b: 4

What is important, is that in arrays and vectors, we can look up certain "lowest element greater than" in amortized constant time by discarding indices which are smaller than every index one by one.

Now, the algorithm. Starting at each (left) index greater than 0, we will find the earliest right index for which the substring bound by [left_index, right_index] is balanced. We do that as follows:

0. Start with left_index = right_index = i for i = 1, ..., n.

1. Read the array of prefix counts for right_index and subtract the prefix counts for left_index - 1 receiving the counts for the substring [left_index, right_index]. Find any letter, which fails the "balance" check. If there is none, you found the shortest balanced substring starting at left_index.

2. Find the first occurrence of the "missing" letter, greater than left_index. Set right_index to the index of that occurrence. Go to step 1 keeping the modified right_index.

For example: starting with left_index = right_index = 1 we see that the number of occurrences of each letter in the substring is 1, 0, 0, 0, so a fails the check. The earliest occurrence of a is 3, so we set right_index = 3. We go back to step 1 receiving a new array of occurrences: 1, 1, 1, 0. Now b fails the check, and its earliest occurrence greater than 1 is 4, so we set right_index to 4. We go to step 1 receiving an array of occurrences 1, 1, 1, 1, which passes the balance check.

Another example: starting with left_index = right_index = 2 we get in step 1 an array of occurrences 0, 0, 1, 0. Now b fails the check. The earliest occurrence of b greater than left_index is 4, so we set right_index to 4. Now we get an array of occurrences 0, 1, 1, 1, so A fails the check. The earliest occurrence of A greater than left_index is 8, so we set right_index to that. Now, the array of occurrences is 2-1, 3-0, 2-0, 1-0, which is 1, 3, 2, 1 and it passes the balance check.

Ultimately we will find the shortest balanced substring to be bB with left_index = 4.

The complexity of this algorithm is O(nl^2) because: we start at n different indices and we perform a maximum of l lookups (for l different letters which can fail the check) in O(1). For each lookup, we have to calculate l differences of prefix sums. But as l is constant (albeit it may be large, like 26), this simplifies to O(n).

I'm using a recursive approach to this; I'm not sure what it's time complexity is though.

The idea is we check what characters in the string are present in both their lower and upper form formats. For any characters that aren't given in both forms, we replace them with a space ' '. We then split the remaining string on ' ' into a list.

In the first case, if we have only one string left after it- we return it's length.

In the second case, if we have no characters left, we return -1.

In the third case, if we have more than one string left, we re-evaluate each of the strings sub-lengths and return the length of the longest string we then evaluate.

    from collections import Counter
    
    def findMutual(s):
        lower = dict(Counter( [x for x in s if x.lower() == x] ))
        upper = dict(Counter( [x for x in s if x.upper() == x] ))
    
        mutual = {}
    
        for charr in lower:
            if charr.upper() in upper:
                mutual[charr] = upper[charr.upper()] + lower[charr]
    
        matching_charrs = ''.join([x if x.lower() in mutual else ' ' for x in s ]).split()
        print(s)
        print(matching_charrs)
        return matching_charrs
    
    
    
    def smallestSubstring(s):
    
        matching_charrs = findMutual(s)
    
        if len(matching_charrs) == 1:
            return(len(matching_charrs[0]))
        elif len(matching_charrs) == 0:
            return(-1)
        else:
            list_lens = []
            for i in matching_charrs:
                list_lens.append(smallestSubstring(i))
            return max(list_lens)                
    
    print(smallestSubstring('azABaabza'))
    print(smallestSubstring('dAcZCbaBz'))
    print(smallestSubstring('TacoCat'))
    print(smallestSubstring('Tt'))
    print(smallestSubstring('T'))
    print(smallestSubstring('TaCc'))