CODEWITHSUNDEEP
stringsortingoptimization
Tricko Treat
Tricko Treat

Reputation: 23

Sorting a string lexicographically in c++

i am new in programming. i just learned strings in c++.

I have N strings and I want to sort them in lexicographical order.(Dictionary order)

How, can i do that as N is quite Big 1 <= N <= 1e5 and size of each string is 1 <= |s| <= 1000.

Also the string is only made of small English alphabets.

I have figured out one method which is sorting them but test cases are tight and giving TLE.

Is there a better Approach for this problem. Please help.

Upvotes: 2

Views: 8029

Answers (1)

Mr.HITMAN
Mr.HITMAN

Reputation: 157

Yes, there are two ways.

  1. Use HASHING.

HOW TO USE ?

  • Create a simple integer array(hash[]) of size 26. Each of its index will denote an alphabet, considering your string is only comprised of small alphabets.
  • Initialize the array to zero.
  • Now traverse the string and for each occurred alphabet in string add its frequency by one in hash[]. For example if 'a' occurred in string then hash[0] = hash[0] + 1;
  • After you are finished with above step. you will have all characters frequency in hash.
  • Now traverse your hash[] and for each index i print all characters until hash[i] becomes zero. It is because, as you want to sort string lexicographically the best way is print all 'a' then all 'b' and so on present in string.
  • Time complexity for above method is O(n*2s).
  • Below is the program
int hash[26]={0};
for( int i = 0 ; i < s.length() ; i++ ) // s.length() returns string length
{
   hash[s[i]-97] += 1; // s[i] - 97 actually returns index for the character
}
char ch;
for( int i = 0 ; i < 26 ; i++ )
{
   ch = i+97; // making the character required
   while(hash[i]) { cout << ch; hash[i] -= 1; } // printing it its frequency times
}
  1. Use nlog(n) sorting
  • In C++ you can use sort() function to sort the strings also.

HOW ?

  • Just write sort( s.begin() , s.end() ) ;
  • Complexity of this method is O(n*|s|log(|s|))
  • Code is below
string s;
cin >> s;
sort( s.begin(); s.end() );
cout << s << endl;

Upvotes: 2

Related Questions