Valid Anagram

 Problem

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = "anagram", t = "nagaram"

Output: true

Example 2:

Input: s = "rat", t = "car"

Output: false

Note:

You may assume the string contains only lowercase alphabets.

Solution

We can compare the frequency of the characters.

import java.util.*;

class Solution {

  public static void main(String[] args) {

    String s = null, t = "";

    System.out.println(solve(s, t));

  }

  private static boolean solve(String s, String t) {

    if(s == null || t == null)

      throw new IllegalArgumentException("bad input");

    char[] freq = new char[26];

    for(char c : s.toCharArray()) {

      freq[c - 'a']++;

    }

    for(char c : t.toCharArray()) {

      freq[c - 'a']--;

      if(freq[c - 'a'] < 0)

        return false;

    }

    for(int i : freq) {

      if(i != 0)

        return false;

    }

    return true;

  }

}

The time complexity is O(max(L1, L2)), space complexity is O(max(L1, L2)), where L1 and L2 is the length of the two strings.

First Unique Character in a String

Problem

Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1.

Examples:

s = "leetcode"

return 0.

s = "loveleetcode"

return 2.

Note: You may assume the string contains only lowercase English letters.

Solution

We can iterate the string characters, create the frequency map, then we iterate it second time, look up the frequency of each character. The first character with frequency 1 is the answer.

import java.util.*;

class Solution {

  

  public static void main(String[] args) {

    String in = "eebb";

    System.out.println(solve(in));

  }

  private static int solve(String str) {

    //leetcode

    Map<Character, Integer> map = new HashMap<>();

    for(char c : str.toCharArray()) {

      map.put(c, map.getOrDefault(c, 0) + 1);

    }

    //l 1, e 3...

    for(int i = 0; i < str.length(); i++) {

      if(map.get(str.charAt(i)) == 1)

        return i;

    }

    return -1;

  }

}

The time complexity is O(N) and space complexity is O(N).

Two Sum

 Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

[11, 2, 6, 15, -1, 10]

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

Solution

We can use one HashMap to store the index of the current value. Later whenever we get a value, we use target - current value as key to lookup the HashMap. If we found it, that is the solution.

import java.util.*;

class Solution {

  

  public static void main(String[] args) {

    int[] arr = new int[]{2, 7, 11, 15};

    int target = 9;

    int[] result = solve(arr, target);

    if(result == null) {

      throw new RuntimeException("impossible");

    }

    System.out.println(result[0] + "," + result[1]);

  }

  //2, 7, 11, 15

  private static int[] solve(int[] arr, int target) {

    Map<Integer, Integer> map = new HashMap<>();

    for(int i = 0; i < arr.length; i++) {

      int other = target - arr[i]; //2

      if(map.get(other) != null) {

        return new int[]{map.get(other), i};

      }

      map.put(arr[i], i);  //7 0

    }

    return null;

  }

}

The time complexity is O(N) and space complexity is O(N).

LRU Cache

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:

Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 );

cache.put(1, 1);

cache.put(2, 2);

cache.get(1);       // returns 1

cache.put(3, 3);    // evicts key 2

cache.get(2);       // returns -1 (not found)

cache.put(4, 4);    // evicts key 1

cache.get(1);       // returns -1 (not found)

cache.get(3);       // returns 3

cache.get(4);       // returns 4

Solution

The shortcut is to use LinkedHashMap with capacity 2. We also need to override

removeEldestEntry

    @Override

    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {

        return size() > capacity; 

    }

The LinkedHashMap implements the eviction with a double linked list. The hashmap maps the key to a double linked list node. Whenever a node is added, it is added after the head node. If the size is bigger 

than capacity, a node is removed from tail. A get operation remove a linked list node, put it at the head. 

import java.util.*;

class Solution {

  public static void main(String[] args) {

    LRUCache cache = new LRUCache(2);

    cache.put(1, 1);

    cache.put(2, 2);

    System.out.println(cache.get(1));       // returns 1

    cache.put(3, 3);    // evicts key 2

    System.out.println(cache.get(2));       // returns -1 (not found)

    cache.put(4, 4);    // evicts key 1

    System.out.println(cache.get(1));       // returns -1 (not found)

    System.out.println(cache.get(3));       // returns 3

    System.out.println(cache.get(4));       // returns 4

  }

  

  static class LRUCache {

    private int capacity = 0;

    private Node head;

    private Node tail;

    private int size;

    private Map<Integer, Node> map = new HashMap<>();

    public LRUCache(int capacity) {

      this.capacity = capacity;

      head = new Node();

      tail = new Node();

      head.next = tail;

      tail.next = head;

    }

    public int get(Integer key) {

      Node node = map.get(key);

      if(node != null) {

        removeNode(node);

        addNode(node);

        return node.val;

      } else {

        return -1;

      }

    }

    

    public void put(Integer key, Integer val) {

      Node node = new Node();

      node.key = key;

      node.val = val;

      addNode(node);

      size++;

      map.put(key, node);

      if(size > capacity) {

        Node tail = removeTail();

        size--;

        map.remove(tail.key);

      }

    }

    

    private void removeNode(Node node) {

      Node pre = node.pre;

      Node next = node.next;

      pre.next = next;

      next.pre = pre;

    }

    

    // head -> node

    // head -> newNode -> node

    private void addNode(Node node) {

      Node next = head.next;

      node.next = next;

      node.pre = head;

      head.next = node;

      next.pre = node;

    }

    

    // noden -> node -> tail

    private Node removeTail() {

      Node node = tail.pre;

      Node pre = node.pre;

      pre.next = tail;

      tail.pre = pre;

      return node;

    }

    

  }

  

  static class Node {

    int key;

    int val;

    Node pre;

    Node next;

  }  

}

All the operations has cost O(1), the space is O(capacity), the extra space came from the double linked list with at most size equal the capacity. 

N-Repeated Element in Size 2N Array

Problem:

N-Repeated Element in Size 2N Array

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

Example 1:

Input: [1,2,3,3]

Output: 3

Example 2:

Input: [2,1,2,5,3,2]

Output: 2

Example 3:

Input: [5,1,5,2,5,3,5,4]

Output: 5

Note:

4 <= A.length <= 10000

0 <= A[i] < 10000

A.length is even

Solution:

We can iterate the array, count each element. The counting can be stored in HashMap datastructure, so that put and get cost O(1). 

import java.util.*;
class Solution {
  public static void main(String...args) {
    int[] arr = new int[]{2,1,2,5,3,2};
    int result = solve(arr);
    System.out.println(result);
  }
  private static int solve(int[] arr) {
    Map<Integer, Integer> map = new HashMap<>();
    for(int i : arr) {
      map.put(i, map.getOrDefault(i, 0) + 1);
    }
    for(Integer i : map.keySet()) {
      if(map.get(i) == arr.length/2)
        return i;
    }
    return Integer.MIN_VALUE;
  }
}

Since we need to iterate the array once and iterate the HashMap once, the time complexity is O(N), the space complexity is O(N) due to the extra space for the HashMap.

Subarrays with K Different Integers

Problem:

Subarrays with K Different Integers

Given a positive integer array and a target k, return the number of subarrays with distinct integers equal to k. The subarray elements need to be contiguous but not necessarily distinct. 

For example, 

given [1,2,3,1,2] and k = 2

the output is 4.

there are 4 subarrays with 2 distinct integers.

[1, 2] [2, 3] [3, 1], [1, 2]

given [1,2,3,1,2] and k = 3

the output is 5.

there are 5 subarrays with 3 distinct integers.

[1, 2, 3], [1, 2, 3, 1] [2, 3, 1] [2, 3, 1, 2] [3, 1, 2]

given [1,2,3,1,2] and k = 0

the output is 5.

given [1,2,3,1,2] and k = 10

the output is 0. 

Solution:

This is a sliding window problem, quite similar to Longest Substring with At Most K Distinct Characters, here we are dealing with integer array instead of character array or string. 

We put the left pointer and right pointer of the sliding window at initial position 0. Then we move the right pointer to expand the sliding window and move the left pointer to shrink the sliding window. 

The right pointer is moved one step at a time, once the distinct integers in the sliding window is equal to k, we start to move the left pointer. Here we need to deal with the following situation:

1, 1, 1, 1, 1, 1, 2, 3, 4

All the subarrays with leading 1s are valid subarrays with distinct integers equal to 4. So we need 2 sliding windows that seak the begin and end of the 1s.

For the datastructure that count the distinct integers in a sliding window, we can use a HashMap to record the repeating time for each integer. 

import java.util.*;
class Solution {
  public static void main(String...args) {
    int[] arr = new int[]{1,2,3,1,2};
    int k = 2;
    System.out.println(subarrays(arr, k));
    k = 3;
    System.out.println(subarrays(arr, k));
    k = 1;
    System.out.println(subarrays(arr, k));
    k = 10;
    System.out.println(subarrays(arr, k));
  }
  public static int subarrays(int[] arr, int k) {
    if(k <= 1 || arr == null) throw new RuntimeException("invalid parameter");
    if(k == 1)
      return arr.length;
    int result = 0;
    SlidingWindow win1 = new SlidingWindow();
    SlidingWindow win2 = new SlidingWindow();
    int lp1 = 0;
    int lp2 = 0;
    for(int i = 0; i < arr.length; i++) {
      win1.add(arr[i]);
      win2.add(arr[i]);
      while(win1.getNumOfUnique() > k) {
        win1.remove(arr[lp1++]);
      }
      while(win2.getNumOfUnique() >= k) {
        win2.remove(arr[lp2++]);
      }
      result += lp2 - lp1;
    }
    return result;
  }
 
  private static class SlidingWindow {
    private int numOfUnique = 0;
    private Map<Integer, Integer> freq = new HashMap<>();
    public void add(int i) {
      freq.put(i, freq.getOrDefault(i, 1));
      if(freq.get(i) == 1) {
        numOfUnique++;
      }
    }
    public void remove(int i) {
      int count = freq.get(i);
      if(count == 1) {
        numOfUnique--;
        freq.remove(i);
      }
    }
    public int getNumOfUnique() {
      return numOfUnique;
    }
  }
}

The time complexity is O(N), the left pointers and right pointer only iterate the integer array once. 

The space complexity is O(N), the HashMap could have size N.

Longest Repeating Character Replacement

Problem:

Given a string s that consists of only uppercase English letters, you can perform at most k operations on that string.

In one operation, you can choose any character of the string and change it to any other uppercase English character.

Find the length of the longest sub-string containing all repeating letters you can get after performing the above operations.

Note:
Both the string's length and k will not exceed 104.

Example 1:

Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.


Example 2:

Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

Solution:

We can use a sliding window, the right edge increase 1 at each step. At each step, we get the sliding window size r - l + 1, we also update the character frequency freq[c] and find the character with the highest frequency maxLen, for all the characters in the sliding window. If r -l + 1 - maxLen <= k, we are able to change all the other characters in the sliding window to the highest frequency character. As a result, we update the result for the current window size, then go to the next step. 

If r -l + 1 - maxLen > k, we should stop expanding, and shrink the sliding window to restore the constraint r -l + 1 - maxLen <= k. We move the left edge one step at a time. At each step, we get the sliding window size r - l + 1, we also update the character frequency freq[c] and find the character with the highest frequency maxLen, for all the characters in the sliding window. 

import java.util.stream.*;
class Solution {
  public static void main(String...args) {
    System.out.println(longestSub("ABAB", 2));
    System.out.println(longestSub("ABAB", 3));
    System.out.println(longestSub("ABAB", 1));
    System.out.println(longestSub("ABAB", 10));
  }
  //AABABBA 1 ---- A 1, B 2
  //    .
  //      .
  public static int longestSub(String str, int k) {//
    int l = 0; //sliding window left pointer
    int maxLen = 0; //max repeating character in the window
    int[] freq = new int['Z' - 'A' + 1];
    int result = 0;
    for(int i = 0; i < str.length(); i++) {
      char c = str.charAt(i);
      freq[c - 'A']++;
      maxLen = Math.max(maxLen, freq[c - 'A']);
      if(i - l + 1 - maxLen <= k) {
        result = Math.max(result, i - l + 1);
      }
     
      while(i - l + 1 - maxLen > k) {
        freq[str.charAt(l++) - 'A']--;
        maxLen = IntStream.of(freq).max().getAsInt();
      }
    }
    return result;
  }
}

The time complexity is O(N), the left edge and right edge iterate the string length at most once. When we move the left edge, for each step, we need to find the maxLen with  maxLen = IntStream.of(freq).max().getAsInt(); the cost is 26 comparisons at most.

The space complexity is O(1), the character frequency counting array has size 26.

Longest Substring with At Most K Distinct Characters

Problem:

Given a string, find the length of the longest substring T that contains at most k distinct characters.

For Example:

Given string "hmhkl" and k = 2

Output: 3

T is "hmh" with length 3, which contains 2 distinct characters.

Solution:

We can solve this problem with sliding window. The left and right pointer initially point to first character. Move the right pointer expands the sliding window and adds new character; while move the left pointer shrink the sliding window and remove old character. We just have to count how many distinct characters are in the sliding window. To achieve that goal, we can use an integer to count the distinct characters and a map to count the repeating times for each character. The map is updated when we add or remove a character, the count is updated when we meet a new character or the map's count for a character decreases to 0. Actually, assuming the string only contains lowercase characters, we can use a size 26 int array to replace the map for the same purpose.

Once we have the count of distinct characters in the sliding window, we can decide when to expand the sliding window and when to shrink the sliding window. When the count is k+1, we need to register a max length then we need to shrink the sliding window until the count is k again.

class Solution {
  public static void main(String...args) {
    System.out.println(longestSub("hmhkl", 2));
    System.out.println(longestSub("klhmhkl", 2));
    System.out.println(longestSub("klhmh", 2));
    System.out.println(longestSub("klhmhklklhmhkl", 2));
    System.out.println(longestSub("bbbbb", 1));
    System.out.println(longestSub("babab", 1));
  }

  public static int longestSub(String str, int k) {
    if(str == null || str.length() == 0)
      return 0;
    int count = 0;
    int[] counter = new int['z' - 'a' + 1]; //26
    int maxLen = 0;
    int tmpMax = 0;
    int l = 0;
    for(int i = 0; i < str.length(); i++) {  //babab
      char c = str.charAt(i); //a
      counter[c - 'a']++;   //b 0, a 1
      tmpMax++;   //2
      if(counter[c - 'a'] == 1) {
        count++;  //2
        if(count > k) {
          maxLen = Math.max(maxLen, tmpMax - 1);  //1
          while(l < i) {
            c = str.charAt(l++); //b
            counter[c - 'a']--;
            tmpMax--;
            if(counter[c - 'a'] == 0) {
              count--;
              break;
            }
          }
        }
      }
    }
    maxLen = Math.max(maxLen, tmpMax);
    return maxLen;
  }
}

The time complexity is O(N), the left and right pointer go through the string only once at most.

The space complexity is O(1), we only has a size 26 array and a few variables for this algorithm.

Subarray Sum Equals K

Problem:

Number of subarrays that Sum to Target

Given an integer array, and a target, return the number of non-empty subarrys that sum to target.

For example, Given array [1, 2, 3] and target 3:
subarray [1, 2] and [3] sum to 3, so the answer is 2.

Solution:

The brutal force solution is to iterate all the indexes, at each position, we iterate all the indexes on the right, calculate the sum and compare with the target. The time complexity is O(N^2) and the space complexity is O(1).

A common pitfall solution is to use sliding window to achieve time complexity O(N) and space complexity O(1) performance. Do you see what's wrong with the following solution?

class Solution {
  public static void main(String...args) {
    int[] arr = new int[]{1, 2, 3};
    int target = 3;
    System.out.println(numOfsubArrays(arr, target));
  }

  /*
  1  2  3
        .
        *
  sum = 3
  count = 2
  */
  public static int numOfsubArrays(int[] arr, int target) {
    int left = 0;
    int n = arr.length;
    int count = 0;
    int sum = 0;
    for(int i = 0; i < arr.length; i++) {
      sum += arr[i];
      if(sum == target)
        count++;
      while(sum > target && left <= i) {
        sum -= arr[left];
        left++;
        if(sum == target)
          count++;
      }
    }
    return count;
  }
}

The code works only if all the elements in the array is positive integer. The above solution is based on the assumption that, when we include a new element in the sliding window, the sum increases, when we remove an old element from the sliding window, the sum decreases. This assumption won't hold if we have negative elements in the subarray.

Actually, if we use a Hashmap to trade space for time, there is a time complexity O(N) and space complexity O(N) solution.

The model is as follows: we iterate from left to right of the array and calculate the sum of elements we saw so far. If we saw a new sum, we put the sum as key and 1 as value to the hashmap. If we saw the same sum later, we increase the value by 1. The reason we build this model is, given any 2 sum[j] and sum[i], the subarray's sum between j and i can be calculated with sum[j] - sum[i]. If the result is equal to k, we found a match.

Now, at each position, we subtract the target from the sum, then use the result as key to look up the hashmap. If we found a match, that means, the current sum minus some previous sum equal to target, which means, the subarray between a previous index and current index sum up to target. We kept saying "some previous sum", how many? It is equal to the value in the hashmap.

import java.util.*;
class Solution {
  public static void main(String...args) {
    int[] arr = new int[]{3, 4, 7, 2, -3, 1, 4, 2};
    int target = 7;
    System.out.println(numOfsubArrays(arr, target));
  }
 
  public static int numOfsubArrays(int[] arr, int target) {
    Map<Integer, Integer> sumCount = new HashMap<>();
    int sum = 0;
    int count = 0;
    for(int i = 0; i < arr.length; i++) {
      sum += arr[i];
      if(sumCount.get(sum - target) != null) {
        count += sumCount.get(sum - target);
      }
      sumCount.put(sum, sumCount.getOrDefault(sum, 1));
    }
    return count;
  }
}

The time complexity is O(N), we need to iterate the array once, the space complexity is O(N), we need a size N hashmap to store the same sum count.

Minimum Window Substring II

Problem:

Given a Source string and a Target string, find the shortest substring in Source string that contains all unique characters in target string.

For Example:

Given source string "YMNZZDXQFHYAZX" and target string "XYZ"

The shortest substring in "YMNZZDXQFHYAZX" that contains "XYZ" is "YAZX"
Note:

If no solution, return the empty string "".
We can assume there is only one unique answer window in source string.

Solution:

The problem is fit for sliding window. We use two pointers to mark a focus window's left and right edge. We slide the right pointer to add more characters to the window for consideration, we move the left pointer to remove characters from the window. For a particular window, we exam the condition to update a result candidate. The remaining design work is now boiling down to when to move right pointer, when to move left pointer. 

For this particular problem, we move the right pointer 1 step at a time until the condition "substring in Source string that contains all unique characters in target string" meets. Once the condition is met, we move the left pointer one step at time, until the condition no longer meet, during the process, we can find the shortest substring end at the right pointer's position that satisfy the condition. 

After that, we move the right pointer in order to restore the condition, then we move the left pointer in order to break the condition, during the process, we will find another shortest substring candidate. 

Then we repeat until the right pointer reach the end of the string.

import java.util.*;
public class Solution {
  public static String shortestSubstring(String s, String t) { //YMNZZDXQFHYAZX XYZ
    if(s.length() == 0 || t.length() == 0) return "";
    HashMap<Character, Integer> counter = new HashMap<>();
    int left = 0, right = 0;
    int minL = 0, minR = Integer.MAX_VALUE;  //10,13
    Set<Character> tt = new HashSet<>();
    for(Character c : t.toCharArray()) {
      tt.add(c);
    }
    while(right < s.length()) {
      char c = s.charAt(right);
     
      if(tt.contains(c)) {
        counter.put(c, counter.getOrDefault(c, 0) + 1);
      }
     
      while(counter.size() == tt.size()) {
        if(right - left < minR - minL) {
          minL = left;
          minR = right;
        }
        char tmp = s.charAt(left);
        if(tt.contains(tmp)) {
          if(counter.get(tmp).equals(1)) {
            counter.remove(tmp);
          } else {
            counter.put(tmp, counter.get(tmp) - 1);
          }
        }
        left++;
      }
      right++;
    }
    if(minR == Integer.MAX_VALUE)
      return "";
    return s.substring(minL, minR+1);
  }
  public static void main(String...args) {
    System.out.println(shortestSubstring("YMNZZDXQFHYAZX", "XYZ"));
  }
}

The time complexity is O(S + T), we iterate Source and Target at least once. The space complexity is O(S + T), the HashSet has size O(T) and the HashMap has size O(T) but the final string could have size O(S). 

Longest Substring Without Repeating Characters

Problem:

Given a string, find the length of the longest substring without repeating characters.

For Example:

Input: "xxyzxzzy"
Output: 3
Explanation: The answer is "xyz", with the length of 3.


Input: "mmmmmm"
Output: 1
Explanation: The answer is "m", with the length of 1.
Example 3:

Input: "hmmqmym"
Output: 3
Explanation: The answer is "qmy", with the length of 3.

Solution:

We can use a sliding window, find all the combinations of the end index and start index, check if substring(start, end) have duplicate character, the start and end index need two loops, check duplicate need another loop. The total cost will be O(N^3).

We can do this smarter.
The duplicate check can be done with a HashMap, which has cost of 1 instead of N.

If substring [start, end) has already been checked for duplicate, then to check duplicate for substring [start, end + 1) is to check if the character at index end is already in the substring [start, end), which is a cost 1 HashMap call.

Anther observation is: if a character has duplicate at index k in the range [i, j), the start index can advance to k + 1, skip all the duplicate check between [i, k]. The reason is, any substring start before k, will bound to find duplicate at current examine index, the only chance for no duplicate substring start at k + 1.

import java.util.*;
class FindLongestSubString {

  //abbcprqmpaq
  private static String getLongest(String word) {
    //sliding window, advance start index and end index
    Map<Character, Integer> nextPos = new HashMap<>();
    int maxLength = 0;
    int startIndex = 0;
    for(int start = 0, end = 0; end < word.length(); end++) {  //end = 10q
      if(nextPos.containsKey(word.charAt(end))) {
        start = Math.max(start, nextPos.get(word.charAt(end)));  //7
      }
      if(end - start + 1 > maxLength) {    //6
          maxLength = end - start + 1;    //6
          startIndex = start;  //2
      }
      nextPos.put(word.charAt(end), end + 1);  //a10;b3;c4;p9;r6;q11;m8
    }
    return word.substring(startIndex, startIndex + maxLength);
  }
  public static void main(String...args) {
    String result = getLongest("abbcprqmpaq");
    System.out.println(result);
    result = getLongest("abbcprqmpaqx");
    System.out.println(result);
    result = getLongest("abbcrqmppaqx");
    System.out.println(result);
    result = getLongest("abbcprqmpazx");
    System.out.println(result);
    result = getLongest("mznhieabbcprqmpazx");
    System.out.println(result);
  }
}

The time complexity is O(N), we need to iterate the word, cost for hashmap is 1. The space complexity is O(N) which is the size of the hashMap

This is a typical sliding window problem, we use a mask to hide the whole string, only reveal a window for part of the string, then study its property. The sliding window has a left and right edge, we move the left edge to mask unconcerned characters, we move the right edge to reveal more character into concern. For this particular problem, we move the right edge 1 step at a time to reveal one more character until visited the whole string. If the new character has been seen before at index k, we can safely move left edge to k+1, ignoring all the substrings before position k. It is because any substring that includes the same character at index k will have duplicate. Now the substring in the sliding window's left and right edge form a candidate for the longest substring without duplicate. To remember the last time we saw a character, we can use a HashMap, however, since the characters are limited, we can use an array for the same purpose, size 128 array for ASCII and 256 for extended ASCII.

public class Solution {
  public static String longestSubString(String str) { //x
    String longest = "";
    int[] lastSeen = new int[256];
    int i = 0, j = 0;
    while(j < str.length()) { //i=2, j=5
      Character c = str.charAt(j++);  //x
      i = Math.max(i, lastSeen[c]);
      lastSeen[c] = j;  //x:5, y:3, z= 4
      if(longest.length() < j - i) {
        longest = str.substring(i, j);  //xyz
      }
    }
    return longest;
  }
  public static void main(String...args) {
    System.out.println(longestSubString("xxyzxzzy"));
  }
}

The time complexity is O(N), we only go through the array once. The space complexity is O(N), the longest substring can only be as long as N.

Word Break

Problem

Word Break

Given a non-empty string and an array of non-empty words, determine if s can be composed by one or more words in the array.

For exampl, 

Given string "atigerisacat" and array [a, tiger, is, cat, deer, mice, not].

Output: true

Given string "twotigersarestillcats" and array [a, tiger, is, cat, deer, mice, not].

Output: false

Solution

We need to exam the string recursively. For a given start index, we increase the end index, then exam if substring(star, end) is in the dictionary. If yes, we then set start = end, then recursively validate the substring(start). Since we validated many substrings again and again in the caller stack, we can trade space for speed by memorize those result. Thus the call stack won't be larger than N. Therefore, the time cost is O(N^2) and space cost is O(N).

import java.util.*;
public class WordBreak {
  public static boolean canBreak(String str, List<String> dic, int start, Boolean[] memo) {
    if(start == str.length()) return true;
    if(memo[start] != null) return memo[start];
    for(int end = start + 1; end <= str.length(); end++) {
      if(dic.contains(str.substring(start, end)) && canBreak(str, dic, end, memo)) {
        memo[start] = true;
        return true;
      }
    }
    memo[start] = false;
    return false;
  }
  public static void main(String...args) {
    String[] dic = new String[]{"a", "tiger", "is", "cat", "deer", "mice", "not"};
    String s = "atigerisacat";
    Boolean[] memo = new Boolean[s.length()];
    System.out.println(canBreak(s, Arrays.asList(dic), 0, memo));
    s = "twotigersarestillcats";
    memo = new Boolean[s.length()];
    System.out.println(canBreak(s, Arrays.asList(dic), 0, memo));
  }
}

Time complexity O(N^2), space complexity O(N).

Binary Tree Vertical Order Traversal

Problem:

Binary Tree Vertical Order Traversal

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Examples 1:

Input: [3,9,20,null,null,15,7]

   3
  /\
 /  \
 9  20
    /\
   /  \
  15   7

Output:

[
  [9],
  [3,15],
  [20],
  [7]
]
Examples 2:

Input: [3,9,8,4,0,1,7]

     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7

Output:

[
  [4],
  [9],
  [3,0,1],
  [8],
  [7]
]

Solution

The node in the same array has the same distance from the middle line, so we can traversal the tree, count the distance from the middle line, when we reaches the leaf, we add the node into a map, the key is the distance from middle line, the value is the array contains this node. We need to traversal the tree, the cost is O(N), we need a map to store the tree nodes, the space cost is O(N). If order of the array does matter, we need to use TreeMap instead of HashMap, insertion of the Nth element cost O(MlogM), M is the total number of columns, so the time cost is still dominated by O(N).

import java.util.*;

public class BSTVerticalOrder {

  Map<Integer, List<Node>> result = new TreeMap<>();

    /*

     3

    /\

   /  \

   9   8

  /\  /\

 /  \/  \

 4  01   7 

 */

  //result: 2-[4];0-[0,1,3];1-[9];-2[7];-1[8];

  public void verticalOrder(Node root, int leftCount) {//3,0; 9,1; 4,2; 0,0;8,-1;1,0;7,-2

    if(root == null) return;

    if(root.left == null && root.right == null) {

      addResult(leftCount, root);

      return;

    } 

    verticalOrder(root.left, leftCount+1);

    verticalOrder(root.right, leftCount-1);

    addResult(leftCount, root);

  }

  

  private void addResult(int leftCount, Node root) {

    List<Node> column = result.get(leftCount);

    if(column == null) {

      column = new ArrayList<>();

      column.add(root);

      result.put(leftCount, column);

    } else {

      column.add(root);

    }

  }

  

  public static void main(String...args) {

    BSTVerticalOrder bstVO = new BSTVerticalOrder();

    Node root = new Node(3, new Node(9, new Node(4, null, null), new Node(0, null, null)), 

                         new Node(8, new Node(1, null, null), new Node(7, null, null)));

    bstVO.verticalOrder(root, 0);

    for(List<Node> column : bstVO.result.values()) {

      column.forEach(i -> System.out.print(" " + i.value));

      System.out.println();

    }

  }

  private static class Node {

    private int value;

    private Node left;

    private Node right;

    public Node(int value, Node left, Node right) {

      this.value = value;

      this.left = left;

      this.right = right;

    }

  }

}

Time cost O(N), space cost O(N).

Reduce string to smallest lexicographical order

Problem

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:

Input: "bcabc"

Output: "abc"

Example 2:

Input: "cbacdcbc"

Output: "acdb"

Solution

The lexicographical order comparison of 2 strings start at index 0, from left to right, compare the characters at the same position, stop at the first position the characters are different.

For example, azzzzzzzz is smaller than baa, because the character a index 0 is different, 'a' is smaller than 'b', the rest of the characters don't matter.

For another examle, aabzzzzz is smaller than aacaa, because the characters at index 0 and 1 are the same, they differ at index 2, and 'b' is smaller than 'c', the rest of the characters don't matter. 

If we scan the character from left to right and decide which one to save and which one to remove. 

For example:

bcabc

we read in b, it ok to keep it, we read in c, bc also makes sense. Now we read in bca, the string doesn't make sense anymore. Keep bc will increase the  lexicographical order, since bca will be larger than a, we should remove bc. Remove them is ok, we won't violate the criteria that each character has to be in the final string, there are another b and c later. Finally we add the rest of bc, abc is the final result, we satisfied the criteria that the lexicographical order is smallest, and we have all the characters.

For another example:

mnzbamnb

we read in mnz, the string makes sense, so we keep them. Now we read in b, the string mnzb doesn't make sense anymore, mnzb is lexicographical larger than b, we should remove mnz. Removing mn is ok, since there are other m and n later. However, remove z is not ok, since z is unique. If we have to keep z, we must keep mn as well because mnz is lexicographical smaller than z. As a result, the unique character z saved all the characters from removing by later characters. We have mnz in the final string, the problem changes to decide what characters in bamnb will be in the final string. mnzba will reduce to mnza, mnzam will be reduced to mnza, because adding a duplicate m increase lexicographical order. mnzan will be reduced to mnza, then we add the b, which is the last appearance of b, therefore unique when we meet it. So the final string is mnzab.

With some observations, we find out that only two kinds of characters left in the final string.

1. global minimal character. Any character comes before this character will increase the lexicographical order, therefore, should be removed. Unless it is unique.
2. unique character. Unique character can not be removed no matter how big it is. As a result, a unique character shields all characters before it from getting removed from the final string. The string before it becomes permanent, we only have to consider the characters after it. A duplicate character becomes unique when we reach the last one of its appearance.

With a stack, we can simulate the above process. From left to right of the string, we push the characters into the stack, before a character enter the stack, it needs to pop out the characters larger than it until the stack is empty or a unique character is met. The character then only enters the stack if it is a unique character so far. Finally, we we reach the end of the string, whatever left in the stack is the final result.

import java.util.*;
public class LexicoGraphicalOrder {
  public static String dedupe(String str) {
    Set<Character> onStack = new HashSet<>();
    Map<Character, Integer> lastIndex = new HashMap<>();
    Stack<Character> stack = new Stack<>();
    int N = str.length(); //8
    //cbacdcbc
    //       .
    //stack  acdb
    //onStack acdb
    for(int i = 0; i < N; i++) {  //c 7, b 6, a 2, d 4
      lastIndex.put(str.charAt(i), i);
    }
    for(int i = 0; i < N; i++) {//7
      char currChar = str.charAt(i);  //c
      if(!onStack.contains(currChar)) {
        while(!stack.isEmpty() && stack.peek() - currChar > 0 && lastIndex.get(stack.peek()) > i) {
          Character lastSeen = stack.peek();  //b
          if(lastSeen - currChar > 0 && lastIndex.get(lastSeen) > i) {
            stack.pop();
            onStack.remove(lastSeen);
          }
        }
        stack.push(currChar);
        onStack.add(currChar);
      }
    }
    StringBuilder sb = new StringBuilder();
    for(char c : stack) {
      sb.append(c);
    }
    return sb.toString();
  }

  public static void main(String...args) {
    System.out.println(dedupe("cbacdcbc"));
    System.out.println(dedupe("mnzamn"));
    System.out.println(dedupe("mnzmnedcbamnnnnnmmmm"));
  }
}

The time complexity is O(N). It is not O(N^2) because no matter how large the string is, the queue size won't be larger than 'z'-'a' which is a constant. For the same reason, the space complexity is also O(N).

Intersection of Two Arrays II

Problem

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]

Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]

Output: [4,9]

Note:

Each element in the result should appear as many times as it shows in both arrays.

The result can be in any order.

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?

What if nums1's size is small compared to nums2's size? Which algorithm is better?

What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Solution

One solution is to sort the arrays, then use 2 pointers to find the solution. The time cost is O(NlogN + MlogM), the space cost is O(1).

import java.util.*;
public class InterSection  {
  public static List<Integer> findInterSection(int[] a, int[] b) {
    //[4 5 9], nums2 = [4 4 8 9 9]
    Arrays.sort(a);
    Arrays.sort(b);
    List<Integer> result = new ArrayList<>();
    int N = a.length; //3
    int M = b.length;  //5
    int i = 0, j = 0;
    while(i < N && j < M) {
      if(a[i] < b[j]) i++; //2
      else if(a[i] > b[j]) j++; //3
      else {
        result.add(a[i]); //4 9
        i++;  //3
        j++;  //4
      }
    }
    return result;
  }
  public static void main(String...args) {
    int[] a = new int[]{1,2,2,1};
    int[] b = new int[]{2,2};
    for(int i : findInterSection(a, b)) {
      System.out.print(" " + i);
    }
  }
}

Another solution is to use a hash map to store the character count in array 1, then go through the array 2, add the elements that exist in the hash map and decrease the count. When the count decrease to 0, we need to remove the element. 

The time cost will be O(M + N), the space cost is O(M)

number permutations with restrictions

Problem

number permutations with restrictions

Given the following 6 numbers 1, 2, 2, 3, 4, 5, write a main function, print out all the permutations that satisfy the limitations.

1. number 4 can not be at the third position from left.

2. 3 and 5 can not be the neighbors.

For example 512234, 412345.

Solution

It is a permutation problem with twists. For permutation problem, backtracing strategy is to branch at each position, only print out at the last position. Here, the constraints need to be applied. 

• 3 and 5 can not be neighbors. We can modify the traceback routing by sending a flag to indicate a constraint is put by the previous position, so we have less choices for branching at current position.
• number 4 can not be at the third position from left. We can check it before printing the string.
• we have duplicate numbers, which can be removed by a Set datastructure.

import java.util.*;
public class PrintNumbers {
  private Set<String> result = new HashSet<>();
  //122345
  public void perm(String str, boolean has4Or5, String remains) {
    if(str.length() == 6) {
      if(str.charAt(2) != '4') {
        System.out.println(str);
        result.add(str);
      }
      return;
    }
 
    for(int i = 0; i < remains.length(); i++) {  //6
      char c = remains.charAt(i);  //1
      if(has4Or5 && (c == '3' || c == '5'))
        continue;
      perm(str + c, (c == '3' || c == '5'), remains.substring(0, i) + remains.substring(i + 1));
    }
  }

  public static void main(String...args) {
    PrintNumbers pn = new PrintNumbers();
    pn.perm("", false, "122345");
    for(String word : pn.result) {
      System.out.println(word);
    }
    System.out.println(pn.result.size());  //198
  }
}

We need to run the permutation, the cost is O(n!), the assumption is substring and string concatenation cost 1. The traceback need to hold the temporary strings in memory, the space cost has high bound O(n!), since java has a string pool, the cost in reality should be much lower.

Another approach is to view permutation problem as un-directed graph traversal. Each node is corresponding to a character. One node can lead to any other nodes except itself. Whenever there are constraints, we have to remove the corresponding edges. For example, remove edges between 3 and 5. The path during a dfs graph traversal for each node is the permutations. The constraints of number 4 can not be at the third position from left can be checked before printing. Duplicate can be removed with Set. The time cost and space cost is no better than the previous approach, but we listed here in order to give an alternative solution to make sure the answer is correct.

import java.util.*;
public class PrintNumbers {
  private Set<String> result2 = new HashSet<>();
  private Set<Integer> visited = new HashSet<>();

  private void graphTraversal() {
    char[] chars = "122345".toCharArray();
    int N = chars.length;
    boolean[][] connected = new boolean[N][N];
    //all connected
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        if(i != j) {
          connected[i][j] = true;
        }
      }
    }
    //remove 3-5 edge
    connected[3][5] = false;
    connected[5][3] = false;
    for(int i = 0; i < N; i++) {
      visited = new HashSet<>();
      dfs(connected, i, "122345".substring(i, i+1));
    }
  }

  private void dfs(boolean[][] connected, int w, String path) {
    visited.add(w);
    if(path.length() == 6 && path.charAt(2) != '4') {
      result2.add(path);
    }
    for(int v = 0; v < connected[w].length; v++) {
      if(connected[w][v] && !visited.contains(v)) {
        dfs(connected, v, path + "122345".substring(v, v+1));
        visited.remove(v);
      }
    }
  }

  public static void main(String...args) {
    PrintNumbers pn = new PrintNumbers();
    pn.graphTraversal();
    for(String word : pn.result2) {
      System.out.println(word);
    }
    System.out.println(pn.result2.size());  //198
  }
}

Time cost O(n!), space cost O(n!) but because of java string pool, this is an over estimate.

Math

The number 198 is calculated this way:

a1 a2 a3 a4 a5 a6

3 constraints:

1. a5 can not be at position 3.
2. a4 and a6 can not be put together.
3. a2 = a3.

The possible states without any constraint: 6!

reason: there are 6 choices for position 1, then 5 choices for position 2, then 4...

Apply constraint 1, a5 can not be at position 3.

I(total) = I(a5 is at position 3) + I(a5 is not at position 3)

I(total) = 6!

I(a5 is at position 3) = 5! 

reason, a5 picked position 3, the rest of the 5 number chose 5 positions. The choices are 5!

As a result, after apply constraint 1, the total number of states that a5 can not be at position 3 is:

I(a5 is not at position 3) = 6! - 5! = 600.

Now additionally Apply constraint 2, a4 and a6 can not be put together.

We need to calculate number of states for (a5 is not at position 3) && (a4 a6 are not together).

I(a5 is not at position 3) = I(a5 is not at position 3 && a4 a6 are together) + I(a5 is not at position 3 && a4 a6 are not together)

I(a5 is not at position 3 && a4 a6 are together) is calculated this way:

We combine a4 a6 into one unit a46. Now the 6 elements permutation become 5 elements permutation. When we choose 5 of the possible start positions for combined element a46, there are 2 cases: 

1. the start position of a46 is 2 or 3
2. the start position of a46 is not 2 or 3

I(a5 is not at position 3 && a4 a6 are together && the start position of a46 is 2 or 3) = 2 x 2 x 4! 

reason: a4 and a6 are interchangeable, so we multiply 2, a45 can choose position 2 or 3, so we multiply another 2, finally, the since a4 or a6 hold the position 3, the rest of the 4 elements can chose any of the 4 positions left without any constraint, so we multiply 4!.

I(a5 is not at position 3 && a4 a6 are together && the start position of a46 is not 2 or 3) = 2 x 3 x 3 x 3!

reason: a4 and a6 are interchangeable, so we multiply 2, a45 can choose position 1, 4, 5, so we multiply 3. For the rest of the 4 elements choose the 4 positions left, a5 can not choose position 3, so it has 3 choices, so we multiply 3, for the rest of the 3 elements choose the rest of 3 positions left, there is no constraint, so we multiply 3!.

As a result, 

I(a5 is not at position 3 && a4 a6 are not together) = I(a5 is not at position 3) - I(a5 is not at position 3 && a4 a6 are together) = 600 - (2x2x4! + 2x3x3x3!) = 396

Finally, we apply the constraint 3, a2 = a3.

I(a5 is not at position 3 && a4 a6 are not together && a2 = a3) = 396/2! = 198

reason: n of the elements are interchangeable,  the n elements suppose to create n! different states, but now they only created 1 state, so we divide n! when apply the constraint.

Replace Words

Problem

In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Solution

We can break the sentence into words, then look up the dictionary. The performance is depends on how to implement dictionary look up. Brutal force is for each word, we can loop through the dictionary words to find a match. The time cost will be N*M*word-length*root-length. HashMap or Trie allow fast string lookup. If we use HashSet, we need to check all the substrings word.substring(0, i) to make sure one of those substrings match a dictionary word. The time cost will be O(Sum-of-N(word-length^2)), the space will be the O(N*word-length + M*root-length) for storing the N words in the sentence the M roots in the dictionary. With Trie, we can find shortest prefix in time proportional to the total number of characters in the N words. The space is the storage for the words and the dictionary. 

class RootReplace {
  private static Trie trie = new Trie();
  public static String replace(String[] dict, String sentence) {
    String[] words = sentence.split(" ");
    StringBuilder sb = new StringBuilder();
    int N = words.length;
    for(int i = 0; i < N; i++) {
      String word = words[i];
      String pre = trie.shortestPrefix(word);
      sb.append(pre == null ? word : pre).append(" ");
    }
    return sb.toString();
  }
  public static void main(String...args) {
    String sentence = "the cattle was rattled by the battery";
    String[] dict = new String[]{"cat", "bat", "rat"};
    for(String pre : dict) {
      trie.put(pre, pre);
    }
    System.out.println(replace(dict, sentence));
  }

  private static class Trie {
    private static int R = 26;
    private Node root;
    private static class Node {
      Node[] next = new Node[R];
      String val;
    }
    public void put(String key, String val) {
      root = put(root, key, val, 0);
    }
    private Node put(Node root, String key, String val, int d) {
      Node x = root;
      if(x == null)
        x = new Node();
      if(key.length() == d) {
        x.val = val;
        return x;
      }
      char c = key.charAt(d);
      x.next[c - 'a'] = put(x.next[c - 'a'], key, val, d+1);
      return x;
    }
    public String shortestPrefix(String key) {
      return shortestPrefix(root, key, 0);
    }
    private String shortestPrefix(Node root, String key, int d) {
      if(root == null) return null;
      if(root.val != null) return root.val;
      if(key.length() == d) return null;
      char c = key.charAt(d);
      return shortestPrefix(root.next[c - 'a'], key, d+1);
    }
  }
}

Time cost O(N*word-length). Space cost O(N*word-length + (8R + 56)M*root-length)

Longest substring without repeated characters

Problem:

Given a string, find the longest substring without repeated characters.
For example: given string "abbcrqmppaq" the output should be "bcrqmp"

Solution:

We can use a sliding window, find all the combinations of the end index and start index, check if substring(start, end) have duplicate character, the start and end index need two loops, check duplicate need another loop. The total cost will be O(N^3).

We can do this smarter.
The duplicate check can be done with a HashMap, which has cost of 1 instead of N.

If substring [start, end) has already been checked for duplicate, then to check duplicate for substring [start, end + 1) is to check if the character at index end is already in the substring [start, end), which is a cost 1 HashMap call.

Anther observation is: if a character has duplicate at index k in the range [i, j), the start index can advance to k + 1, skip all the duplicate check between [i, k]. The reason is, any substring start before k, will bound to find duplicate at current examine index, the only chance for no duplicate substring start at k + 1.

import java.util.*;
class FindLongestSubString {

  //abbcprqmpaq
  private static String getLongest(String word) {
    //sliding window, advance start index and end index
    Map<Character, Integer> nextPos = new HashMap<>();
    int maxLength = 0;
    int startIndex = 0;
    for(int start = 0, end = 0; end < word.length(); end++) {  //end = 10q
      if(nextPos.containsKey(word.charAt(end))) {
        start = Math.max(start, nextPos.get(word.charAt(end)));  //7
      }
      if(end - start + 1 > maxLength) {    //6
          maxLength = end - start + 1;    //6
          startIndex = start;  //2
      }
      nextPos.put(word.charAt(end), end + 1);  //a10;b3;c4;p9;r6;q11;m8
    }
    return word.substring(startIndex, startIndex + maxLength);
  }
  public static void main(String...args) {
    String result = getLongest("abbcprqmpaq");
    System.out.println(result);
    result = getLongest("abbcprqmpaqx");
    System.out.println(result);
    result = getLongest("abbcrqmppaqx");
    System.out.println(result);
    result = getLongest("abbcprqmpazx");
    System.out.println(result);
    result = getLongest("mznhieabbcprqmpazx");
    System.out.println(result);
  }
}

The time complexity is O(N), we need to iterate the word, cost for hashmap is 1. The space complexity is O(N) which is the size of the hashMap

Group Anagrams

Problem:

Given a group of words, return the grouped anagrams.
For example, given {"pea", "tea", "ate", "ape", "eat", "root"}
the output should be
{
{"eat", "tea", "ate"},
{"ape", "pea"},
{"root"}
}

solution:

The anagrams has the same characters, once sorted, they become the same string. We can group them with a hashMap. 

import java.util.*;
class Anagrams {
  private static void getAnagrams(String[] words) {
    Map<String, Set<String>> groups = new HashMap<>();
    for(String word : words) {
      char[] chars = word.toCharArray();
      Arrays.sort(chars);
      String tmp = new String(chars);
      if(groups.get(tmp) == null) {
        Set<String> group = new HashSet<>();
        group.add(word);
        groups.put(tmp, group);
      } else {
        groups.get(tmp).add(word);
      }
    }
    groups.values().forEach(System.out::println);
  }
 
  public static void main(String...args) {
    String[] words = new String[] {"pea", "tea", "ate", "ape", "eat", "root"};
    getAnagrams(words);
  }
}

we iterate the words list cost N, sort each word cost logw, w is the length of the word, so the time complexity is O(NlogW), the space complexity is O(N).