Java: O(N) time complexity, O(1) space


  • 0
    R

    public class Solution {
    public String minWindow(String s, String t) {

        Map<Character, Integer> map = new HashMap<>();
        int count = 0;
        String str = "";
    
    
        for (char c : t.toCharArray()) {
            if (!map.containsKey(c)) {
                map.put(c, 1);
            } else {
                map.put(c, map.get(c) + 1);
            }
        }
    
        count = map.size();
    
        int j = 0;
    
        int minLen = Integer.MAX_VALUE;
        int startIndex = 0;
        for (int i = 0;  i < s.length(); i++) {
    
            while (j < s.length()) {
                char currentChar = s.charAt(j);
                if (count == 0) {
                    break;
                } else if (map.containsKey(currentChar)) {
                    map.put(currentChar, map.get(currentChar) - 1);
                    if (map.get(currentChar) == 0) {
                        --count;
    
                    }
                }
                
                ++j;
            }
    
            if (count == 0 && minLen > j - i) {
                startIndex = i;
                minLen = j - i;
            }
    
            char removeChar = s.charAt(i);
            if(map.containsKey(removeChar)){
                map.put(removeChar, map.get(removeChar) + 1);
                if(map.get(removeChar) > 0) {
                    count++;
                }
            }
    
        }
    
       if (minLen == Integer.MAX_VALUE) {
            return "";
       }
        
        return s.substring(startIndex, startIndex + minLen);
    }
    

    }


  • 0
    T

    @rogeryu23 Thanks for posting your solution. I'm trying to understand why it's O(1) space? if s.length = n and t.length = m, shouldn't it b O(n) time, O(m) space?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.