Created
March 11, 2018 06:51
-
-
Save jianminchen/00d5a2cbb401d603b3cdb06a6db4e9c3 to your computer and use it in GitHub Desktop.
Smallest substring of all characters - mock interview - review peer code, very good practice
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.io.*; | |
import java.util.*; | |
class Solution { | |
/* | |
left=0 right=0 | |
min | |
x, y, y, z | |
y . y . z y zyx | |
zyx | |
*/ | |
static String getShortestUniqueSubstring(char[] arr, String str) { | |
// your code goes here | |
if(arr == null || arr.length == 0 || str == null || str.length() == 0){ | |
return ""; | |
} | |
int[] count = new int[256]; | |
for(char ch : arr){ | |
count[ch]++; | |
} | |
int cnt = arr.length; | |
int left = 0; | |
int right = 0; | |
int min = Integer.MAX_VALUE; | |
int minLeft = -1; | |
int minRight = -1; | |
while(right < str.length()){ | |
char ch = str.charAt(right); | |
count[ch]--; | |
if(count[ch] >= 0){ | |
cnt--; | |
} | |
while(cnt <= 0){ | |
if(min > right-left+1){ | |
min = right-left+1; | |
minLeft = left; | |
minRight = right; | |
} | |
char prev = str.charAt(left); | |
count[prev]++; | |
if(count[prev] > 0){ | |
cnt++; // break the loop, prev is in unique char array | |
} | |
left++; | |
} | |
right++; | |
} | |
if(minLeft == -1 && minRight == -1){ | |
return ""; | |
} | |
return str.substring(minLeft,minRight+1); | |
} | |
public static void main(String[] args) { | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment