Longest Substring Without Repeating Characters (LeetCode String)

Question: Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

Idea: Two pointers.  Use two pointers leftBound and i to maintain a slide window. Use a hashset<characters appeared> to cache the characters in the window. The pointer i traverses from left to right. If string[i] is a character appeared in the hashset, push leftBound forward and pop the corresponding character until string[i] can be added into the window (the same character appeared before was popped). If string[i] is a character not in the hashset, push i forward to check the next character.

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   public int lengthOfLongestSubstring(String s) {  
     if(s.length()<=1)  
       return s.length();  
     HashSet<Character> found=new HashSet<Character>();  
     int leftBound=0;  
     int result=0;  
     for(int i=0;i<s.length();i++)  
     {  
       char c=s.charAt(i);  
       while(found.contains(c)&&leftBound<s.length())  
       {  
         char cur=s.charAt(leftBound);  
         found.remove(cur);  
         leftBound++;  
       }  
       found.add(c);  
       result=Math.max(result,found.size());  
     }  
     return result;  
   }  
 }  

Valid Palindrome (LeetCode Two Pointers)

Question: Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Idea: First transfer the whole string to lower case. Then use two pointers i, j to scan the string. i scans from left to right, j scans from right to left. If a character is not alphanumeric, just skip it.

Time: O(n) Space: O(1)

Code with toLowerCase():

 public class Solution {  
   public boolean isPalindrome(String s) {  
     s=s.toLowerCase();  
     int i=0;  
     int j=s.length()-1;  
     while(i<j)  
     {  
       if(notAN(s.charAt(i)))  
       {  
         i++;  
         continue;  
       }  
       if(notAN(s.charAt(j)))  
       {  
         j--;  
         continue;  
       }  
       if(s.charAt(i++)!=s.charAt(j--))  
         return false;  
     }  
     return true;  
   }  
   public boolean notAN(char c)  
   {  
     if(c>='a'&&c<='z')  
       return false;  
     if(c>='0'&&c<='9')  
       return false;  
     return true;  
   }  
 }  

Code without APIs:

 public class Solution {  
   public boolean isPalindrome(String s) {  
     if(s==null||s.length()==0)  
       return true;  
     int left=0;  
     int right=s.length()-1;  
     while(left<right)  
     {  
       int codeLeft=getCode(s.charAt(left));  
       if(codeLeft==-1)  
       {  
         left++;  
         continue;  
       }  
       int codeRight=getCode(s.charAt(right));  
       if(codeRight==-1)  
       {  
         right--;  
         continue;  
       }  
       if(codeLeft!=codeRight)  
         return false;  
       left++;  
       right--;  
     }  
     return true;  
   }  
   public int getCode(char c)  
   {  
     if(c>='0'&&c<='9')  
       return (int)c;  
     if(c>='a'&&c<='z')  
       return (int)c;  
     if(c>='A'&&c<='Z')  
     {  
       return (int)(c-'A'+'a');  
     }  
     return -1;  
   }  
 }  

Implement strStr() (LeetCode Two Pointers)

Question: Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Idea: I used the brute force method by comparing the substrings one by one. There are other algorithms, e.g. KMP which can achieve better performance.

Time: O(n^2) Space: O(1)

Code:

 public class Solution {  
   public int strStr(String haystack, String needle) {  
     for(int i=0;i<haystack.length()-needle.length()+1;i++)  
     {  
       int j=0;  
       for(j=0;j<needle.length();j++)  
       {  
         if(haystack.charAt(i+j)!=needle.charAt(j))  
           break;  
       }  
       if(j==needle.length())  
         return i;  
     }  
     return -1;  
   }  
 }  

Remove Nth Node From End of List (LeetCode Linked List)

Question: Given a linked list, remove the nth node from the end of list and return its head.
For example,
   Given linked list: 1->2->3->4->5, and n = 2.
   After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.

Idea: First add a dummy head at the front of the input linked list, since the original head may be the node to be removed. Then use two pointers "slower" and "faster" to traverse the list. Let the faster run n steps, then let the faster and the slower run simultaneously. Since the faster is n steps ahead of the slower, when faster.next reach the end (null), the slower.next is the nth node which needs to be removed.

Time: O(n) Space: O(1)

Code: 

 public class Solution {  
   public ListNode removeNthFromEnd(ListNode head, int n) {  
     ListNode dummy=new ListNode(0);  
     dummy.next=head;  
     ListNode slower=dummy;  
     ListNode faster=dummy;  
     for(int i=0;i<n;i++)  
       faster=faster.next;  
     while(faster.next!=null)  
     {  
       slower=slower.next;  
       faster=faster.next;  
     }  
     slower.next=slower.next.next;  
     return dummy.next;  
   }  
 }  

Remove Duplicates from Sorted List II (LeetCode Linked List)

Question: Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Idea: First add a dummy node at the front of the input list, since the head node may also be removed.  Then use a pointer "cur" to traverse the list. For each "cur", check whether the next a few elements are duplicates by starting an runner from cur.next.next and compare the value with cur.next. If the runner ran 0 step, means no duplicates, otherwise skip the nodes the runner has passed.

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   public ListNode deleteDuplicates(ListNode head) {  
     if(head==null||head.next==null)  
       return head;  
     ListNode dummy=new ListNode(0);  
     dummy.next=head;  
     ListNode cur=dummy;  
     while(cur.next!=null)  
     {  
       ListNode start=cur.next;  
       ListNode runner=start.next;  
       while(runner!=null&&runner.val==start.val)  
         runner=runner.next;  
       if(start.next=runner)  
         cur=start;  
       else  
         cur=runner;  
     }  
     return dummy.next;  
   }  
 }  

Partition List (LeetCode Linked List)

Question: Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Idea: Two pointers.
1) First add a dummy head in the beginning of the linked list to deal with the cases when the current head>= x that a <x node needs to be added before the current head.
2) Use two pointers: lessTail and pre. lessTail is to remember the last digit <x. pre is used to traverse the list.
3) When pre.next is a value >=x, just push pre forward.
4) When pre.next is a value <x, we need to swap it to right behind lessTail. As in the example in the question, when pre=3, pre.next=2, we need to swap the 2 to the back of 1 (lessTail). In this case, the element 2 is cut from the list and moved to the back of 1. So push lessTail forward by 1 step, but keep pre=3 the same since pre.next=5 is right the node we are going to check in the next run.

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   public ListNode partition(ListNode head, int x) {  
     if(head==null||head.next==null)  
       return head;  
     ListNode dummy=new ListNode(Integer.MIN_VALUE);  
     dummy.next=head;  
     ListNode lessTail=dummy;  
     while(lessTail.next!=null&&lessTail.next.val<x)  
       lessTail=lessTail.next;  
     if(lessTail.next==null)  
       return dummy.next;  
     ListNode pre=lessTail.next;  
     while(pre.next!=null)  
     {  
       if(pre.next.val<x)  
       {  
         ListNode cur=pre.next;  
         pre.next=pre.next.next;  
         cur.next=lessTail.next;  
         lessTail.next=cur;  
         lessTail=lessTail.next;  
       }  
       else  
       {  
         pre=pre.next;  
       }  
     }  
     return dummy.next;  
   }  
 }  

Two Sum II - Input array is sorted (LeetCode Array)

Question: Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Idea: Since this array is sorted, we can use two pointers (left, right) to point to the start and the end of the array. If the sum is bigger than target, make the sum smaller by decrease the right pointer, otherwise increase the left pointer to make the sum bigger. The loop ends when the sum is equal to the target. Take care the output index is the original index+1.

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   public int[] twoSum(int[] numbers, int target) {  
     int left=0;  
     int right=numbers.length-1;  
     int[] result=new int[2];  
     while(left<right)  
     {  
       int sum=numbers[left]+numbers[right];  
       if(sum==target)  
       {  
         result[0]=left+1;  
         result[1]=right+1;  
         return result;  
       }  
       if(sum<target)  
         left++;  
       else  
         right--;  
     }  
     return result;  
   }  
 }  

Sort Colors (LeetCode Array)

Question: Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.


Idea: Another way of thinking this problem is to move all the 0’s to the front of the array and move all the 2’s to the end of the array. So we use scan the array from left to right and use two pointers to remember the positions to move 0’s and 2’s to. Once we find a 0, move it to p0, p0++; once we find a 2, move it to p2, p2--; if it is 1, just go forward.
Since both p0 and the scanner, e.g. i, start from 0, they need to skip the 0’s in the front together. So when A[i]==0, both p0 and i increase 1.
Since the end of the original array may be 2, so the swap may swap two 2’s. Therefore i can not go forward in handling 2’s.

Time: O(n) Space: O(1)

Code:

 <pre style="font-family:arial;font-size:12px;border:1px dashed #CCCCCC;width:99%;height:auto;overflow:auto;background:#f0f0f0;;background-image:URL(https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj_4ttYwMl_uJzWpFN_i6Br26Ka-UAuQurT862HR7CPovBTgDYQCBanMOLWbaQOGbH0WYA43qWxXoN4PqliLI_FkbKJCx7qwClhykGbIBdArsNfC-u2A40ptxiu2kvmgHmI8MShLaH4fbtl/s320/codebg.gif);padding:0px;color:#000000;text-align:left;line-height:20px;"><code style="color:#000000;word-wrap:normal;"> public class Solution {   
   public void sortColors(int[] A) {   
     int p0=0;   
     int p2=A.length-1;   
     int i=0;   
     while(i&lt;=p2)   
     {   
      switch(A[i])   
      {   
       case 0:    
        swap(A,i,p0);   
        p0++;   
        i++;   
        break;   
       case 1:    
        i++;   
        break;   
       case 2:   
        swap(A,i,p2);   
        p2--;   
        break;   
      }   
     }   
   }   
    public void swap(int[] A, int i, int j)   
    {   
       int tmp=A[i];   
       A[i]=A[j];   
       A[j]=tmp;   
    }   
  }   
 </code></pre>  

Remove Element (LeetCode Array)

Question: Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Idea: The basic idea is to move the matched instances to the end of the array. Use two pointers i, j.  i moves from left to right, j moves from right to left. Whenever i is pointing to an instance, swap (num[i], num[j]), move j leftward (do not move i since num[j] may also be an instance); otherwise move i rightward.

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   public int removeElement(int[] A, int elem) {  
     int i=0;  
     int j=A.length-1;  
     while(i<=j)  
     {  
       if(A[i]==elem)  
       {  
         swap(A,i,j);  
         j--;  
       }  
       else  
         i++;  
     }  
     return j+1;  
   }  
   public void swap(int[] A, int i,int j)  
   {  
     int tmp=A[i];  
     A[i]=A[j];  
     A[j]=tmp;  
   }  
 }  

Remove Duplicates from Sorted Array II (LeetCode Array)

Question: Follow up for "Remove Duplicates": What if duplicates are allowed at most twice?
For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].

Idea: Use two pointers i, j. i points to the index of last valid number. Use j to scan the array from left to right. If num[i]==num[i-1]==num[j], "continue"; otherwise copy num[j] to num[++i].

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   public int removeDuplicates(int[] A) {  
     if(A==null)  
       return 0;  
     if(A.length<=2)  
       return A.length;  
     int i=1;  
     for(int j=i+1;j<A.length;j++)  
     {  
       if(A[i]==A[i-1]&&A[i]==A[j])  
         continue;  
       else  
         A[++i]=A[j];  
     }  
     return i+1;  
   }  
 }  

Remove Duplicates from Sorted Array (LeetCode Array)

Question: Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].

Idea: Use two pointers i, j. i points to the last unique number, use j to scan the array from left to right. Since this is a sorted array, whenever num[j]!=num[i], it indicates a new unique number. We increase i by 1 and copy num[j] to the new position i pointing at, then continue increasing j. When j finishes scanning all the numbers, return the result.

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   public int removeDuplicates(int[] A) {  
     if(A==null||A.length==0)  
       return 0;  
     int i=0;  
     for(int j=i+1;j<A.length;j++)  
     {  
       if(A[i]!=A[j])  
         A[++i]=A[j];  
     }  
     return i+1;  
   }  
 }  

Container With Most Water (LeetCode Array)

Question:  Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.

Idea: Use two pointers to maintain a sliding window. For each window, get its area and compare with the result. The window starts with the maximum width (0, length-1). If the height[left] is smaller than height[right], move the left pointer forward (vice era). This is because moving the pointer will decrease the width. If we keep the min(heigh[left],height[right]) in the next comparison, the area size can not be larger than the current. So we just need to move the shorter of the two pointers.

Time: O(n) Space: O(1)

Code: 

 public class Solution {  
   public int maxArea(int[] height) {  
     if(height==null||height.length<=1)  
       return 0;  
     int i=0;  
     int j=height.length-1;  
     int result=0;  
     while(i<j)  
     {  
       result=Math.max(result,(j-i)*Math.min(height[i],height[j]));  
       if(height[i]>height[j])  
         j--;  
       else  
         i++;  
     }  
     return result;  
   }  
 }  

3Sum (LeetCode Array)

Question: Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)

Idea: First sort the array. Then use three pointers (i,j,k) to denote the triplet (a,b,c). Fix i, use j,k to maintain a sliding window. If the current sum is 0, add to result; if the current sum <0, move the left pointer forward, if the current sum>0, move the right pointer backward. Skip the continuously same numbers to avoid duplication.

Time: O(n^2) Space: O(1)

Code: 

 public class Solution {  
   public List<List<Integer>> threeSum(int[] num) {  
     List<List<Integer>> result=new ArrayList<List<Integer>>();  
     if(num==null||num.length<3)  
     {  
       return result;  
     }  
     Arrays.sort(num);  
     for(int i=0;i<num.length-2;i++)  
     {  
       if(i>0&&num[i]==num[i-1])  
         continue;  
       int j=i+1;  
       int k=num.length-1;  
       while(j<k)  
       {  
         int curSum=num[i]+num[j]+num[k];  
         if(curSum<=0)  
         {  
           if(curSum==0)  
             result.add(Arrays.asList(num[i],num[j],num[k]));  
           j++;  
           while(j<k&&num[j]==num[j-1])  
             j++;  
         }  
         else  
         {  
           k--;  
           while(j<k&&num[k]==num[k+1])  
             k--;  
         }  
       }  
     }  
     return result;  
   }  
 }  

3Sum Closest (LeetCode Array)

Question: Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Idea: First sort the array. Use three pointers (i,j,k) to denote the three integers. Fix i, and use j,k to maintain a sliding window. If num[i]+num[j]+num[k]<target, move the left pointer forward, otherwise move the right pointer backward. Since there may be duplicated elements in the array, skip them to avoid repeated calculation, although this will not reduce the worst case time complexity.

Time: O(n^2) Space: O(1)

Code:  

 public class Solution {  
   public int threeSumClosest(int[] num, int target) {  
     int closestSoFar=num[0]+num[1]+num[2];  
     Arrays.sort(num);  
     for(int i=0;i<num.length-2;i++)  
     {  
       if(i>0&&num[i]==num[i-1])  
         continue;  
       int j=i+1;  
       int k=num.length-1;  
       while(j<k)  
       {  
         int curSum=num[i]+num[j]+num[k];  
         if(curSum==target)  
           return target;  
         else if(curSum<target)  
         {  
           j++;  
           while(j<k&&num[j]==num[j-1])  
             j++;  
         }  
         else  
         {  
           k--;  
           while(j<k&&num[k]==num[k+1])  
             k--;  
         }  
         if(Math.abs(target-closestSoFar)>Math.abs(target-curSum))  
           closestSoFar=curSum;  
       }  
     }  
     return closestSoFar;  
   }  
 }  

4Sum (LeetCode HashMap)

Question: Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.
    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

Idea: Use four pointers (i, j, k, l) to represent the quadruplet (a,b,c,d). First sort the array. Then fix i, j and use k, l to maintain a window. If the sum is smaller than the target, move k forward; otherwise move l backward. Remember to skip the duplicated elements.

Time: O(n^3) Space: O(1)

Code:

 public class Solution {  
   public List<String> anagrams(String[] strs) {  
     List<String> result=new ArrayList<String>();  
     if(strs==null||strs.length==0)  
     {  
       return result;  
     }  
     HashMap<String,ArrayList<Integer>> map=new HashMap<String,ArrayList<Integer>>();  
     for(int i=0;i<strs.length;i++)  
     {  
       String sorted=specialSort(strs[i]);  
       if(map.containsKey(sorted))  
       {  
         map.get(sorted).add(i);  
       }  
       else  
       {  
         ArrayList<Integer> tmp=new ArrayList<Integer>();  
         tmp.add(i);  
         map.put(sorted,tmp);  
       }  
     }  
     for(String s:map.keySet())  
     {  
       if(map.get(s).size()>=2)  
       {  
         for(int i:map.get(s))  
         {  
           result.add(strs[i]);  
         }  
       }  
     }  
     return result;  
   }  
   public String specialSort(String s)  
   {  
     HashMap<Character,Integer> map=new HashMap<Character,Integer>();  
     for(char c:s.toCharArray())  
     {  
       if(map.containsKey(c))  
       {  
         map.put(c,map.get(c)+1);  
       }  
       else  
       {  
         map.put(c,1);  
       }  
     }  
     StringBuilder builder=new StringBuilder();  
     for(char c='a';c<='z';c++)  
     {  
       if(map.containsKey(c))  
       {  
         int counter=0;  
         while(counter<map.get(c))  
         {  
           builder.append(c);  
           counter+=1;  
         }  
       }  
     }  
     return builder.toString();  
   }  
 }  

Longest Substring with At Most Two Distinct Characters (LeetCode HashMap)

Question: Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example, Given s = “eceba”,
T is "ece" which its length is 3.

Idea: Use two pointers (left, right) to maintain a sliding window. Use a HashMap to cache the elements and their counts in the sliding window. If the HashMap has at most 2 keys, move the right pointer forward; otherwise move the left pointer forward until the HashMap has one empty spot to add another key. The loop ends when the right pointer reaches the end of the string s and the window is valid. Update the result whenever the right pointer moves forward, since moving the left pointer only decreases the window width.

Time: O(n) Space: O(n)

Code: 

 public class Solution {  
   public int lengthOfLongestSubstringTwoDistinct(String s) {  
     if(s.length()<=2)  
     {  
       return s.length();  
     }  
     HashMap<Character,Integer> found=new HashMap<Character,Integer>();  
     int leftBound=0;  
     int result=0;  
     for(int i=0;i<s.length();i++)  
     {  
       char c=s.charAt(i);  
       if(found.containsKey(c))  
       {  
         found.put(c,found.get(c)+1);  
       }  
       else  
       {  
         while(found.size()==2)  
         {  
           char leftest=s.charAt(leftBound);  
           found.put(leftest,found.get(leftest)-1);  
           leftBound+=1;  
           if(found.get(leftest)==0)  
           {  
             found.remove(leftest);  
           }  
         }  
         found.put(c,1);  
       }  
       int sum=0;  
       for(int value:found.values())  
       {  
         sum+=value;  
       }  
       result=Math.max(result,sum);  
     }  
     return result;  
   }  
 }  

Max Points on a Line (LeetCode HashMap)

Question: Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Idea: Brute force. For each point i, construct lines with all the other points. The other points may be at the same place, or vertical (slope=+Infinite) or horizontal (slope=+0). Since the lines are constructed from point i, once the slope of line (i->j) is the same as a line constructed before, j is on a line constructed before. When calculating the slope, take care 0.0!=-0.0==0.0/-1 in Java.

Time: O(n^2) Space:O(n)

Code: 

 public class Solution {  
   public int maxPoints(Point[] points) {  
     if(points.length==0)  
     {  
       return 0;  
     }  
     HashMap<Double,Integer> counter=new HashMap<Double,Integer>();  
     int result=1;  
     for(int i=0;i<points.length;i++)  
     {  
       counter.clear();  
       counter.put((double)Integer.MAX_VALUE,1);  
       int dup=0;  
       for(int j=i+1;j<points.length;j++)  
       {  
         if(points[i].x==points[j].x&&points[i].y==points[j].y)  
         {  
           dup+=1;  
           continue;  
         }  
         double slope=(points[i].x==points[j].x)?Integer.MAX_VALUE:0.0+(0.0+points[i].y-points[j].y)/(0.0+points[i].x-points[j].x);  
         if(counter.containsKey(slope))  
         {  
           counter.put(slope,counter.get(slope)+1);  
         }  
         else  
         {  
           counter.put(slope,2);  
         }  
       }  
       for(int number:counter.values())  
       {  
         result=Math.max(result,number+dup);  
       }  
     }  
     return result;  
   }  
 }  

Minimum Window Substring (LeetCode HashMap)

Question: 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.

Idea: Use two pointers to keep a sliding window. If the window does not contain T, move the right boundary forward. If the window contains T, keep moving the left boundary forward until the window no longer contains T. The loop ends when the right boundary of the window reaches the right boundary of S and the window does not contain T. Update the minimum window size whenever a new valid (containing T) window is visited.

Time: O(n)  Space: O(n)

Code:

 public class Solution {  
   public String minWindow(String S, String T) {  
     if(S.length()==0||T.length()==0)  
     {  
       return "";  
     }  
     HashMap<Character,Integer> toFind=new HashMap<Character,Integer>();  
     for(int i=0;i<T.length();i++)  
     {  
       char c=T.charAt(i);  
       if(toFind.containsKey(c))  
       {  
         toFind.put(c,toFind.get(c)+1);  
       }  
       else  
       {  
         toFind.put(c,1);  
       }  
     }  
     HashMap<Character,Integer> found=new HashMap<Character,Integer>();  
     int leftBound=0;  
     int counter=0;  
     String result="";  
     for(int i=0;i<S.length();i++)  
     {  
       char c=S.charAt(i);  
       if(!toFind.containsKey(c))  
       {  
         continue;  
       }  
       if(found.containsKey(c))  
       {  
         found.put(c,found.get(c)+1);  
       }  
       else  
       {  
         found.put(c,1);  
       }  
       if(found.get(c)<=toFind.get(c))  
       {  
         counter++;  
       }  
       if(counter==T.length())  
       {  
         while(leftBound<S.length())  
         {  
           char left=S.charAt(leftBound);  
           if(!toFind.containsKey(left))  
           {  
             leftBound++;  
             continue;  
           }  
           if(found.get(left)>toFind.get(left))  
           {  
             found.put(left,found.get(left)-1);  
             leftBound++;  
             continue;  
           }  
           break;  
         }  
         if(result.equals("")||result.length()>i-leftBound+1)  
         {  
           result=S.substring(leftBound,i+1);  
         }  
       }  
     }  
     return result;  
   }  
 }