Minimize length of prefix of string S containing all characters of another string T | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int getPrefixLength ( string srcStr , string targetStr ) { if ( targetStr . length ( ) == 0 ) return 0 ; transform ( srcStr . begin ( ) , srcStr . end ( ) , srcStr . begin ( ) , :: tolower ) ; transform ( targetStr . begin ( ) , targetStr . end ( ) , targetStr . begin ( ) , :: tolower ) ; map < char , int > dictCount ; int nUnique = 0 ; for ( char ch : targetStr ) { if ( dictCount . find ( ch ) == dictCount . end ( ) ) { nUnique += 1 ; dictCount [ ch ] = 0 ; } dictCount [ ch ] += 1 ; } for ( int i = 0 ; i < srcStr . length ( ) ; i ++ ) { char ch = srcStr [ i ] ; if ( dictCount . find ( ch ) == dictCount . end ( ) ) continue ; dictCount [ ch ] -= 1 ; if ( dictCount [ ch ] == 0 ) nUnique -= 1 ; if ( nUnique == 0 ) return ( i + 1 ) ; } return -1 ; } int main ( ) { string S = " MarvoloGaunt " ; string T = " Tom " ; cout << getPrefixLength ( S , T ) ; return 0 ; }