Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/00d5a2cbb401d603b3cdb06a6db4e9c3 to your computer and use it in GitHub Desktop.
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
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