Question

An online coin dealer offers bags of coins that are guaranteed to contain at least one full set. Given a string comprised of lowercase letters in the range ascii[a-z), where each letter represents a coin type, determine the length of the shortest substring that contains at least one of each type of coin. Example: coins = dabbcabcd The list of all characters in the string is (a, b, c, d]. Two of the substrings that contain all letters are dabbc and abcd. The shortest substring that contains all of the letters is 4 characters long. Function Description Complete the function fewestCoins in the editor below. fewestCoins has the following parameter: string coins: a string Return int: the length of the shortest substring that contains at least one of each characters in coins Constraints

LANGUAGE: JAVA

Answer 1

java code:

import java.util.*;
import java.util.LinkedList;
import java.util.Queue;

public class Main
{
public boolean containALL(String str)
{ //check whether string contain all character (a,b,c,d) or not.
boolean flagA=false,flagB=false,flagC=false,flagD=false;
  
for(int i=0;i<str.length();i++)
{
if(str.charAt(i)=='a')
flagA=true;
  
if(str.charAt(i)=='b')
flagB=true;
  
if(str.charAt(i)=='c')
flagC=true;
  
if(str.charAt(i)=='d')
flagD=true;
}
  
if(flagA&&flagB&&flagC&&flagD)
return true;
return false;
  
}
   public static void main(String[] args) {

       Main obj=new Main();
       Scanner sc=new Scanner(System.in);
       String input=sc.nextLine();
       int n=input.length(),min=1000000;
  
   Queue<Integer> q
= new LinkedList<>();
  
for(int i=0;i<n;i++)
{
if(input.charAt(i)=='a')
q.add(i); // all position of character 'a'.
}
Iterator value = q.iterator();
while (value.hasNext()) {
int index=q.peek();
  
for(int i=4;i<n;i++) //loop from min length i.e 4 to n.
{ //check all substring starting with character 'a'.
if(index+i<=n)
{
String substr2 = input.substring(index,index+i);
if(obj.containALL(substr2))
{
if(min>i-index+1)
{
min=i; //get the minimum length.
}
}
}
}
  
q.remove();
  
}
System.out.println(min);
   }
}

Output:

dabbcabcd 4