Virkne ar maksimālo unikālo rakstzīmju skaitu
Ņemot vērā virkņu masīvu, uzdevums ir izdrukāt virkni ar maksimālais skaits unikālie varoņi.
Piezīme:
- Virknes sastāv no mazajiem burtiem.
- Ja pastāv vairākas virknes, izdrukājiet jebkuru no tām.
Piemēri:
Ievade: arr[] = ['abc' "geeksforgeeks" "gfg" "kods"]
Izvade: "geeks par geeks"
Paskaidrojums: 'abc' ir 3 unikālas rakstzīmes, 'geeksforgeeks' ir 7 unikālas rakstzīmes
'gfg' ir 3 unikālas rakstzīmes 'kodā' ir 4 unikālas rakstzīmes.Ievade: arr[] = ['sveiki' 'pasaule' 'programmēšana' 'zebra']
Izvade: "programmēšana"
Paskaidrojums: 'programmēšanai' ir 8 unikālas rakstzīmes, kas ir maksimālais.
Pieeja:
Ideja ir sistemātiski pārbaudīt katras virknes izsekošanu, kuri mazie burti tajā parādās, izmantojot Būla masīvu, saskaitot šīs unikālās rakstzīmes un sekojot līdzi tam, kura virkne ir devusi lielāko skaitu līdz šim.
Soli pa solim pieeja:
- Atkārtojiet katru kolekcijas virkni.
- Katrai virknei izmantojiet Būla masīvu, lai atzīmētu, kuri burti ir.
- Saskaitiet, cik atšķirīgu burtu tika atzīmēts kā klātesošs.
- Ja šis skaits pārsniedz iepriekšējo maksimālo, atjauniniet maksimumu un atcerieties šīs virknes pozīciju.
- Atgrieziet virkni ar vislielāko atrasto unikālo rakstzīmju skaitu.
// 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 ));
Izvade
geeksforgeeks
Laika sarežģītība: O(n*m) kur n ir dotā virkņu masīva lielums un m ir lielākais virknes izmērs dotajā masīvā.
Palīgtelpa: O(1)
