Q-9 PepCoding | Smallest Substring Of A String Containing All Unique Characters Of Itself
Tue Jan 24 2023 12:50:50 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
import java.util.*;
public class Main {
public static int solution(String str){
int ans = Integer.MAX_VALUE;
HashSet<Character> set1 = new HashSet<>();
for(int i = 0 ;i < str.length();i++){
char ch = str.charAt(i);
if(set1.contains(ch)==false)
set1.add(ch);
}
HashMap<Character,Integer> set2 = new HashMap<>();
int i = -1 ;
int j = -1 ;
while(true){
boolean f1 = false;
boolean f2 = false;
//accquire
while(j < str.length()-1 && set2.size() < set1.size() ){
j++;
char ch = str.charAt(j);
set2.put(ch , set2.getOrDefault(ch,0)+1);
f1 = true;
}
//store ans and release
while(i < j && set2.size() == set1.size() ){
String pans = str.substring(i+1 , j+1);
if(pans.length() < ans)
ans = pans.length();
i++;
char ch = str.charAt(i);
if(set2.get(ch) ==1)
set2.remove(ch);
else
set2.put(ch , set2.getOrDefault(ch,0)-1);
f2 = true;
}
if(f1 == false && f2 == false)
break;
}
return ans;
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
String str = scn.next();
System.out.println(solution(str));
}
}
content_copyCOPY
https://www.pepcoding.com/resources/data-structures-and-algorithms-in-java-levelup/hashmap-and-heaps/smallest-substring-of-a-string-containing-all-unique-characters-of-itself-official/ojquestion
Comments