Karakterlánc maximális számú egyedi karakterrel
Adott egy sztring tömb, a feladat az, hogy kinyomtassuk a karakterláncot a maximális szám egyedi karakterekből.
Jegyzet:
- A karakterláncok kisbetűkből állnak.
- Ha több karakterlánc létezik, nyomtassa ki bármelyiket.
Példák:
Bemenet: arr[] = ['abc' 'geeksforgeeks' 'gfg' 'kód']
Kimenet: "geek a strébereknek"
Magyarázat: Az 'abc'-nek 3 egyedi karaktere van, a 'geeksforgeeks'-nek 7 egyedi karaktere van
A "gfg" 3 egyedi karakterből áll, a "code" 4 egyedi karakterből áll.Bemenet: arr[] = ['hello' 'világ' 'programozás' 'zebra']
Kimenet: 'programozás'
Magyarázat: A 'programozás' 8 egyedi karakterből áll, ami a maximum.
Megközelítés:
Az ötlet az, hogy szisztematikusan megvizsgáljuk az egyes karakterláncokat, hogy nyomon kövesse, mely kisbetűk jelennek meg benne, egy logikai tömb segítségével, amely megszámolja azokat az egyedi karaktereket, és nyomon követi, hogy melyik karakterlánc eredményezte eddig a legtöbb értéket.
Lépésről lépésre megközelítés:
- Ismételje meg a gyűjtemény egyes karakterláncait.
- Minden karakterlánchoz használjon logikai tömböt, hogy megjelölje, mely betűk vannak jelen.
- Számolja meg, hány különböző betűt jelölt meg jelenlevőként.
- Ha ez a szám meghaladja az előző maximumot, frissítse a maximumot, és emlékezzen a karakterlánc pozíciójára.
- A legtöbb talált egyedi karaktert tartalmazó karakterláncot adja vissza.
// 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 ));
Kimenet
geeksforgeeks
Időbeli összetettség: O(n*m) ahol n az adott karakterlánc tömb mérete és m az adott tömbben jelenlévő karakterlánc legnagyobb mérete.
Segédtér: O(1)
