567. Permutation in String

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.


Example 1:
Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:
Input:s1= "ab" s2 = "eidboaoo"
Output: False
 
Example 3:
Input:s1= "abb" s2 = "abaab"
Output: False

Example 4:
Input:s1= "abba" s2 = "abaab"
Output: True

Note:

The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s1.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        
        // map
        // a 0
        // b 0
        // size 0
        // 
        // abba
        // abaab
        // l
        //     r
        int size = map.size(); // 2
        int l = 0;
        int r = 0;
        while (r < s2.length()) {
            char c = s2.charAt(r); // c
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
                if (map.get(c) == 0) {
                    size--;
                }
            }
            r++;
            
            while (size == 0) {
                char tempc = s2.charAt(l);
                if (map.containsKey(tempc)) {
                    map.put(tempc, map.get(tempc) + 1);
                    if (map.get(tmpec) > 0) {
                        size++;
                    }
                    if (r - l == s1.length()) {
                        return true;
                    }
                }
            }
            l++;
        }
        return false;
    }
}

Sliding window

s1: a b c 

s2: c b e a b a b a c d
    l
    r
-------------------------
Map Key : Value
     a  :  0
     b  :  1
     c  :  1

Size of map: 0

Time complexity: `O(Ns1 + Ns2)`.

Space complexity: `O(1)`.

## 05/19/20.

Online Stock Span
Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock's price for the current day.

The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price.

For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].

Stack: 100, 85
op.  :  1 ,  6

output stream: 1, 1, 1, 2, 1, 4, 6
    

Example 1:

Input: ["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
Output: [null,1,1,1,2,1,4,6]
Explanation: 
First, S = StockSpanner() is initialized.  Then:
S.next(100) is called and returns 1,
S.next(80) is called and returns 1,
S.next(60) is called and returns 1,
S.next(70) is called and returns 2,
S.next(60) is called and returns 1,
S.next(75) is called and returns 4,
S.next(85) is called and returns 6.

Note that (for example) S.next(75) returned 4, because the last 4 prices
(including today's price of 75) were less than or equal to today's price.
 

Note:

Calls to StockSpanner.next(int price) will have 1 <= price <= 10^5.
There will be at most 10000 calls to StockSpanner.next per test case.
There will be at most 150000 calls to StockSpanner.next across all test cases.
The total time limit for this problem has been reduced by 75% for C++, and 50% for all other languages.

class StockSpanner {

    private Stack<Stock> stack;
    
    public StockSpanner() {
        stack = new Stack<>();
    }
        
    public int next(int price) {
        int span = 1;
        Stock stock = new Stock(price, span);
        while (!stack.isEmpty() && stock.price >= stack.peek().price) {
            stock.span += stack.pop().span;
        }
        
        stack.push(stock);
        return stock.span;
    }
}

class Stock {
    int price;
    int span;
    
    public Stock(int price, int span) {
        this.price = price;
        this.span = span;
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */

["StockSpanner","next","next","next","next","next","next","next","next","next","next"]
[[],[28],[14],[28],[35],[46],[53],[66],[80],[87],[88]]
Input:
["StockSpanner","next","next","next","next","next","next","next","next","next","next"]
[[],[28],[14],[28],[35],[46],[53],[66],[80],[87],[88]]
Output:
[null,1,1,2,4,5,6,7,8,9,10]
Expected:
[null,1,1,3,4,5,6,7,8,9,10]