Zeichenfolge mit maximaler Anzahl eindeutiger Zeichen
Bei einem gegebenen Array von Strings besteht die Aufgabe darin, den String mit dem auszugeben maximale Anzahl einzigartiger Charaktere.
Notiz:
- Zeichenfolgen bestehen aus Kleinbuchstaben.
- Wenn mehrere Zeichenfolgen vorhanden sind, drucken Sie eine davon aus.
Beispiele:
Eingang: arr[] = ['abc' 'geeksforgeeks' 'gfg' 'code']
Ausgabe: „Geeks für Geeks“
Erläuterung: „abc“ hat 3 einzigartige Zeichen, „geeksforgeeks“ hat 7 einzigartige Zeichen
„gfg“ hat 3 eindeutige Zeichen, „code“ hat 4 eindeutige Zeichen.Eingang: arr[] = ['hello' 'world' 'programming' 'zebra']
Ausgabe: 'Programmierung'
Erläuterung: „Programmierung“ hat maximal 8 eindeutige Zeichen.
Ansatz:
Die Idee besteht darin, jede Zeichenfolge systematisch zu untersuchen und zu verfolgen, welche Kleinbuchstaben darin vorkommen. Dazu wird ein boolesches Array verwendet, das diese eindeutigen Zeichen zählt und verfolgt, welche Zeichenfolge bisher die höchste Anzahl ergeben hat.
Schritt-für-Schritt-Ansatz:
- Durchlaufen Sie jede Zeichenfolge in der Sammlung.
- Verwenden Sie für jede Zeichenfolge ein boolesches Array, um zu markieren, welche Buchstaben vorhanden sind.
- Zählen Sie, wie viele verschiedene Buchstaben als vorhanden markiert wurden.
- Wenn diese Anzahl das vorherige Maximum überschreitet, aktualisieren Sie das Maximum und merken Sie sich die Position dieser Zeichenfolge.
- Gibt die Zeichenfolge mit der höchsten Anzahl gefundener eindeutiger Zeichen zurück.
// 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 ));
Ausgabe
geeksforgeeks
Zeitkomplexität: O(n*m) Wo N ist die Größe des angegebenen String-Arrays und M ist die größte Größe der im angegebenen Array vorhandenen Zeichenfolge.
Hilfsraum: O(1)
