Minimum Window Substring

76. Minimum Window Substring

LintCode-32.Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S

class Solution {
    func minWindow(_ s: String, _ t: String) -> String {
        var dict: [Character: Int] = [:]
        for c in t {
            dict[c, default: 0] += 1
        }
        
        var len = Int.max, count = t.count, start = 0
        var result = ""
        var startIndex = s.startIndex, iIndex = s.startIndex
        
        for i in 0..<s.count {
            let c = s[iIndex]
            
            if let charCount = dict[c] {
                dict[c] = charCount - 1
                
                if charCount >= 1 {
                    count -= 1
                }
            }
            
            while count == 0 {
                if i - start + 1 < len {
                    len = i - start + 1
                    result = String(s[startIndex...iIndex])
                }
                
                let startChar = s[startIndex]
                if let charCount = dict[startChar] {
                    dict[startChar] = charCount + 1
                    
                    if charCount >= 0 {
                        count += 1
                    }
                }
                start += 1
                startIndex = s.index(after: startIndex)
            }
            
            iIndex = s.index(after: iIndex)
        }
        
        return result
    }
}
public class Solution {
    public String minWindow(String s, String t) {
        String result = "";

        if (s == null || s.length() == 0 || t == null || t.length() == 0) {
            return result;
        }

        Map<Character, Integer> map = new HashMap<>();
        
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }
        
        int start = 0, counter = t.length();
        int min = Integer.MAX_VALUE;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (!map.containsKey(c)) {
                continue;
            }
            
            map.put(c, map.get(c) - 1);
                
            if (map.get(c) >= 0) {
                counter--;
            }
                
            while (counter == 0) {
                if (min > i - start + 1) {
                    min = i - start + 1;
                    result = s.substring(start, i + 1);
                }
                
                char startChar = s.charAt(start);
                if (map.containsKey(startChar)) {
                    map.put(startChar, map.get(startChar) + 1);
                    
                    if (map.get(startChar) > 0) {
                        counter++;
                    }
                }
                    
                start++;
            }
        }
        
        return result;
    }
}

Hope this helps,
Michael

DigitalOcean Referral Badge