Minimize length of prefix of string S containing all characters of another string T | Java program for the above approach ; Base Case - if T is empty , it matches 0 length prefix ; Convert strings to lower case for uniformity ; Update dictCount to the letter count of T ; If new character is found , initialize its entry , and increase nUnique ; Increase count of ch ; Iterate from 0 to N ; i - th character ; Skip if ch not in targetStr ; Decrease Count ; If the count of ch reaches 0 , we do not need more ch , and can decrease nUnique ; If nUnique reaches 0 , we have found required prefix ; Otherwise ; Driver code
import java . util . * ; public class Main { public static int getPrefixLength ( String srcStr , String targetStr ) { if ( targetStr . length ( ) == 0 ) return 0 ; srcStr = srcStr . toLowerCase ( ) ; targetStr = targetStr . toLowerCase ( ) ; HashMap < Character , Integer > dictCount = new HashMap < > ( ) ; int nUnique = 0 ; for ( char ch : targetStr . toCharArray ( ) ) { if ( dictCount . containsKey ( ch ) != true ) { nUnique += 1 ; dictCount . put ( ch , 0 ) ; } dictCount . replace ( ch , dictCount . get ( ch ) + 1 ) ; } for ( int i = 0 ; i < srcStr . length ( ) ; i ++ ) { char ch = srcStr . charAt ( i ) ; if ( dictCount . containsKey ( ch ) != true ) continue ; dictCount . replace ( ch , dictCount . get ( ch ) - 1 ) ; if ( dictCount . get ( ch ) == 0 ) nUnique -= 1 ; if ( nUnique == 0 ) return ( i + 1 ) ; } return - 1 ; } public static void main ( String [ ] args ) { String S = " MarvoloGaunt " ; String T = " Tom " ; System . out . println ( getPrefixLength ( S , T ) ) ; } }