String Problems — Meta and Google Favourites

Meta/Google String Favourites

1. Longest Substring Without Repeating Characters

def lengthOfLongestSubstring(s):
    last_seen = {}
    l = res = 0
    for r, c in enumerate(s):
        if c in last_seen and last_seen[c] >= l:
            l = last_seen[c]+1
        last_seen[c] = r
        res = max(res, r-l+1)
    return res

2. Valid Parentheses

def isValid(s):
    stack = []
    pairs = {')':'(', ']':'[', '}':'{'}
    for c in s:
        if c in '([{': stack.append(c)
        elif not stack or stack[-1] != pairs[c]: return False
        else: stack.pop()
    return not stack

3. String to Integer (atoi)

def myAtoi(s):
    s = s.lstrip()
    if not s: return 0
    sign = 1
    i = 0
    if s[0] in '+-':
        if s[0] == '-': sign = -1
        i = 1
    res = 0
    while i < len(s) and s[i].isdigit():
        res = res*10 + int(s[i])
        i += 1
    res *= sign
    return max(-2**31, min(2**31-1, res))

JavaScript

function lengthOfLongestSubstring(s){
    const last=new Map(); let l=0,res=0;
    for(let r=0;r<s.length;r++){if(last.has(s[r])&&last.get(s[r])>=l)l=last.get(s[r])+1;last.set(s[r],r);res=Math.max(res,r-l+1);}
    return res;
}
function isValid(s){
    const stk=[],p={')':'(',']}':'[','}':'{'}; // Note: map closing to opening
    const m={')':'(',']':'[','}':'{'};
    for(const c of s){if('([{'.includes(c))stk.push(c);else if(!stk.length||stk[stk.length-1]!==m[c])return false;else stk.pop();}
    return!stk.length;
}

Java

public int lengthOfLongestSubstring(String s){
    Map<Character,Integer>last=new HashMap<>();int l=0,res=0;
    for(int r=0;r<s.length();r++){char c=s.charAt(r);if(last.containsKey(c)&&last.get(c)>=l)l=last.get(c)+1;last.put(c,r);res=Math.max(res,r-l+1);}
    return res;
}

C++

#include <unordered_map>
#include <string>
using namespace std;
int lengthOfLongestSubstring(string s){
    unordered_map<char,int>last; int l=0,res=0;
    for(int r=0;r<(int)s.size();r++){if(last.count(s[r])&&last[s[r]]>=l)l=last[s[r]]+1;last[s[r]]=r;res=max(res,r-l+1);}
    return res;
}

C

int lengthOfLongestSubstring(char*s){int last[128];memset(last,-1,sizeof(last));int l=0,res=0,n=strlen(s);for(int r=0;r<n;r++){if(last[(int)s[r]]>=l)l=last[(int)s[r]]+1;last[(int)s[r]]=r;if(r-l+1>res)res=r-l+1;}return res;}