Merkkijono, jossa on enimmäismäärä yksilöllisiä merkkejä
Kun on annettu joukko merkkijonoja, tehtävänä on tulostaa merkkijono enimmäismäärä ainutlaatuisista hahmoista.
Huomautus:
- Merkkijonot koostuvat pienistä kirjaimista.
- Jos useita merkkijonoja on olemassa, tulosta mikä tahansa niistä.
Esimerkkejä:
Syöte: arr[] = ['abc' 'geeksforgeeks' 'gfg' 'koodi']
Lähtö: "nörtejä nörteille"
Selitys: "abc" sisältää 3 ainutlaatuista merkkiä "geeksforgeeks" sisältää 7 ainutlaatuista merkkiä
'gfg' sisältää 3 ainutlaatuista merkkiä 'koodissa' on 4 yksilöivää merkkiä.Syöte: arr[] = ['hei' 'maailma' 'ohjelmointi' 'zebra']
Lähtö: 'ohjelmointi'
Selitys: 'ohjelmointi' sisältää 8 yksilöllistä merkkiä, mikä on enimmäismäärä.
Lähestyä:
Ajatuksena on tutkia systemaattisesti jokaista merkkijonoa, joka seuraa, mitkä pienet kirjaimet siinä esiintyvät, käyttämällä boolen taulukkoa, joka laskee nuo ainutlaatuiset merkit ja seuraa, mikä merkkijono on tuottanut eniten tähän mennessä.
Askel askeleelta lähestymistapa:
- Iteroi jokaisen kokoelman merkkijonon läpi.
- Käytä jokaiselle merkkijonolle loogista taulukkoa merkitäksesi, mitkä kirjaimet ovat läsnä.
- Laske kuinka monta eri kirjainta on merkitty läsnä oleviksi.
- Jos tämä määrä ylittää edellisen maksimiarvon, päivitä maksimi ja muista tämän merkkijonon sijainti.
- Palauta merkkijono, jossa on eniten löydettyjä yksilöllisiä merkkejä.
// C++ code to find string with maximum // number of unique characters. #include using namespace std ; // Function to find string with // maximum number of unique characters. string maxString ( vector < string > & arr ) { int n = arr . size (); int index = -1 maxCnt = 0 ; for ( int i = 0 ; i < n ; i ++ ) { vector < bool > map ( 26 false ); for ( int j = 0 ; j < arr [ i ]. length (); j ++ ) { map [ arr [ i ][ j ] - 'a' ] = true ; } // Find number of unique char int cnt = 0 ; for ( int j = 0 ; j < 26 ; j ++ ) { if ( map [ j ] == true ) cnt ++ ; } // If unique count is greater if ( cnt > maxCnt ) { maxCnt = cnt ; index = i ; } } return arr [ index ]; } int main () { vector < string > arr = { 'abc' 'geeksforgeeks' 'gfg' 'code' }; cout < < maxString ( arr ); return 0 ; }
Java // Java code to find string with maximum // number of unique characters. import java.util.* ; class GfG { // Function to find string with // maximum number of unique characters. static String maxString ( String [] arr ) { int n = arr . length ; int index = - 1 maxCnt = 0 ; for ( int i = 0 ; i < n ; i ++ ) { boolean [] map = new boolean [ 26 ] ; for ( int j = 0 ; j < arr [ i ] . length (); j ++ ) { map [ arr [ i ] . charAt ( j ) - 'a' ] = true ; } // Find number of unique char int cnt = 0 ; for ( int j = 0 ; j < 26 ; j ++ ) { if ( map [ j ] == true ) cnt ++ ; } // If unique count is greater if ( cnt > maxCnt ) { maxCnt = cnt ; index = i ; } } return arr [ index ] ; } public static void main ( String [] args ) { String [] arr = { 'abc' 'geeksforgeeks' 'gfg' 'code' }; System . out . println ( maxString ( arr )); } }
Python # Python code to find string with maximum # number of unique characters. # Function to find string with # maximum number of unique characters. def maxString ( arr ): n = len ( arr ) index = - 1 maxCnt = 0 for i in range ( n ): map = [ False ] * 26 for j in range ( len ( arr [ i ])): map [ ord ( arr [ i ][ j ]) - ord ( 'a' )] = True # Find number of unique char cnt = sum ( 1 for j in range ( 26 ) if map [ j ]) # If unique count is greater if cnt > maxCnt : maxCnt = cnt index = i return arr [ index ] if __name__ == '__main__' : arr = [ 'abc' 'geeksforgeeks' 'gfg' 'code' ] print ( maxString ( arr ))
C# // C# code to find string with maximum // number of unique characters. using System ; class GfG { // Function to find string with // maximum number of unique characters. static string maxString ( string [] arr ) { int n = arr . Length ; int index = - 1 maxCnt = 0 ; for ( int i = 0 ; i < n ; i ++ ) { bool [] map = new bool [ 26 ]; for ( int j = 0 ; j < arr [ i ]. Length ; j ++ ) { map [ arr [ i ][ j ] - 'a' ] = true ; } // Find number of unique char int cnt = 0 ; for ( int j = 0 ; j < 26 ; j ++ ) { if ( map [ j ] == true ) cnt ++ ; } // If unique count is greater if ( cnt > maxCnt ) { maxCnt = cnt ; index = i ; } } return arr [ index ]; } static void Main () { string [] arr = { 'abc' 'geeksforgeeks' 'gfg' 'code' }; Console . WriteLine ( maxString ( arr )); } }
JavaScript // JavaScript code to find string with maximum // number of unique characters. // Function to find string with // maximum number of unique characters. function maxString ( arr ) { let n = arr . length ; let index = - 1 maxCnt = 0 ; for ( let i = 0 ; i < n ; i ++ ) { let map = new Array ( 26 ). fill ( false ); for ( let j = 0 ; j < arr [ i ]. length ; j ++ ) { map [ arr [ i ]. charCodeAt ( j ) - 'a' . charCodeAt ( 0 )] = true ; } // Find number of unique char let cnt = 0 ; for ( let j = 0 ; j < 26 ; j ++ ) { if ( map [ j ] === true ) cnt ++ ; } // If unique count is greater if ( cnt > maxCnt ) { maxCnt = cnt ; index = i ; } } return arr [ index ]; } let arr = [ 'abc' 'geeksforgeeks' 'gfg' 'code' ]; console . log ( maxString ( arr ));
Lähtö
geeksforgeeks
Aika monimutkaisuus: O(n*m) jossa n on annetun merkkijonotaulukon koko ja m on annetussa taulukossa olevan merkkijonon suurin koko.
Aputila: O(1)
