מחרוזת עם מספר מקסימלי של תווים ייחודיים

בהינתן מערך של מחרוזות, המשימה היא להדפיס את המחרוזת עם מספר מקסימלי של דמויות ייחודיות.

פֶּתֶק:

  • מחרוזות מורכבות מתווים קטנים.
  • אם קיימות מחרוזות מרובות, הדפס כל אחת מהן.

דוגמאות:  

קֶלֶט: arr[] = ['abc' 'geeksforgeeks' 'gfg' 'קוד']
תְפוּקָה: "חנונים לגיקים" 
הֶסבֵּר: ל'abc' יש 3 תווים ייחודיים ל'geeksforgeeks' יש 7 תווים ייחודיים
ל'gfg' יש 3 תווים ייחודיים ל'קוד' יש 4 תווים ייחודיים.

קֶלֶט: arr[] = ['שלום' 'עולם' 'תכנות' 'זברה']
תְפוּקָה: 'תִכנוּת' 
הֶסבֵּר: ל'תכנות' יש 8 תווים ייחודיים שזה המקסימום.

גִישָׁה:

הרעיון הוא לבחון באופן שיטתי כל מחרוזת העוקבת אחר האותיות הקטנות המופיעות בה באמצעות מערך בוליאני הסופר את אותם תווים ייחודיים ועוקב אחר איזו מחרוזת הניבה את הספירה הגבוהה ביותר עד כה.

גישה צעד אחר צעד:

  1. חזור על כל מחרוזת באוסף.
  2. עבור כל מחרוזת השתמש במערך בוליאני כדי לסמן אילו אותיות קיימות.
  3. ספור כמה אותיות שונות סומנו כנוכחות.
  4. אם ספירה זו חורגת מהמקסימום הקודם עדכן את המקסימום וזכור את מיקומה של המחרוזת.
  5. החזר את המחרוזת עם המספר הגבוה ביותר של תווים ייחודיים שנמצאו.
C++
   // 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  ));   

תְפוּקָה
geeksforgeeks 

מורכבות זמן: O(n*m) אֵיפֹה נ הוא הגודל של מערך המחרוזות הנתון ו מ הוא הגודל הגדול ביותר של המחרוזת הקיימת במערך הנתון.
מרחב עזר: O(1)