Another from the archives. In my old notes I tried a few different approaches. Ultimately this one feels a little “brute-force-y”, here is what I got:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0;
for (int i = 0; i < s.size(); i++) {
for (int l = std::max(res, 1); l + i <= s.size(); l++) {
std::bitset<256> seen;
bool bad = false;
for (int j = i; j < i + l; j++) {
if (seen.test(s[j])) {
bad = true;
break;
}
seen.set(s[j]);
}
if (!bad) {
res = std::max(res, l);
} else {
// i i our starting point, a longer l won't help here.
break;
}
}
}
return res;
}
};
Thoughts
- The “length” iteration (how i, l, j indexes interact) is pretty interesting. Comes up rarely, but in thinking about many collections of substrings.
- The final “break” (with the comment above it) is necessary.
- I wanted to port this to Python—my old archives are in C++. But it lacks a bitset class, and its range loops aren’t amenable to the length-based iteration (or at least, I don’t know how to adapt them).
I doubt my solution is the right one. What is the official Leetcode solution? Oh I like it! Does this make the cut as an interview question? I don’t know, I am skeptical. More string questions here.