Length of smallest substring of a given string which contains another string as subsequence | Java program to implement the above approach ; Function to find the length of smallest substring of a having string b as a subsequence ; Stores the characters present in string b ; Find index of characters of a that are also present in string b ; If character is present in string b ; Store the index of character ; Flag is used to check if substring is possible ; Assume that substring is possible ; Stores first and last indices of the substring respectively ; For first character of string b ; If the first character of b is not present in a ; If the first character of b is present in a ; Remove the index from map ; Update indices of the substring ; For the remaining characters of b ; If index possible for current character ; If no index is possible ; If no more substring is possible ; Update the minimum length of substring ; Return the result ; Driver code ; Given two string
import java . util . ArrayList ; import java . util . HashMap ; class GFG { static int minLength ( String a , String b ) { HashMap < Character , Integer > Char = new HashMap < > ( ) ; for ( int i = 0 ; i < b . length ( ) ; i ++ ) { Char . put ( b . charAt ( i ) , Char . getOrDefault ( b . charAt ( i ) , 0 ) + 1 ) ; } HashMap < Character , ArrayList < Integer > > CharacterIndex = new HashMap < > ( ) ; for ( int i = 0 ; i < a . length ( ) ; i ++ ) { char x = a . charAt ( i ) ; if ( Char . containsKey ( x ) ) { if ( CharacterIndex . get ( x ) == null ) { CharacterIndex . put ( x , new ArrayList < Integer > ( ) ) ; } CharacterIndex . get ( x ) . add ( i ) ; } } int len = Integer . MAX_VALUE ; int flag ; while ( true ) { flag = 1 ; int firstVar = 0 , lastVar = 0 ; for ( int i = 0 ; i < b . length ( ) ; i ++ ) { if ( i == 0 ) { if ( CharacterIndex . containsKey ( i ) ) { flag = 0 ; break ; } else { int x = CharacterIndex . get ( b . charAt ( i ) ) . get ( 0 ) ; CharacterIndex . get ( b . charAt ( i ) ) . remove ( CharacterIndex . get ( b . charAt ( i ) ) . get ( 0 ) ) ; firstVar = x ; lastVar = x ; } } else { int elementFound = 0 ; for ( var e : CharacterIndex . get ( b . charAt ( i ) ) ) { if ( e > lastVar ) { elementFound = 1 ; lastVar = e ; break ; } } if ( elementFound == 0 ) { flag = 0 ; break ; } } } if ( flag == 0 ) { break ; } len = Math . min ( len , Math . abs ( lastVar - firstVar ) + 1 ) ; } return len ; } public static void main ( String [ ] args ) { String a = " abcdefababaef " ; String b = " abf " ; int len = minLength ( a , b ) ; if ( len != Integer . MAX_VALUE ) { System . out . println ( len ) ; } else { System . out . println ( " Impossible " ) ; } } }