Superior character in a string using Moore’s voting algorithm

Write a function which takes a string and prints the superior character(if it exists), otherwise prints “No Superior Character”. A superior character in a string ‘str’ of size n is an element that appears more than n/2 times (and hence there is at most one such character).

Examples :

Input : df5&sdfdddd
Output : d

Input : #a$a%a@a%a45aaaaa
Output : a

Try your approach in the W3Colleges IDE first.

Approach :

This is the best approach.

Using Moore’s Voting Algorithm :

This is a two step process.

Note : This Method only works when we are given that superior character do exist in the string, otherwise this method won’t work , as in the problem definition we said that superior character may or may not exist but for applying this approach you can assume that superior character do exist in the given input array

1. The first step gives the character that may be superior character in the string. If there is a superior character in a string, then this step will definitely return superior character , otherwise it will return candidate for superior character .
2. Check if the character obtained from above step is superior character .This step is necessary as we are not always sure that character return by first step is superior character .

1. Finding a Candidate :

The algorithm for first phase that works in O(n) is known as Moore’s Voting Algorithm. Basic idea of the algorithm is that if we cancel out each occurrence of an character e with all the other character that are different from e then e will exist till end if it is a superior character .

findCandidate(str, size)
1.  Initialize index and count of majority character 
     maj_index = 0, count = 1
2.  Loop for i = 1 to size – 1
    (a) If a[maj_index] == a[i]
          count++
    (b) Else
        count--;
    (c) If count == 0
          maj_index = i;
          count = 1
3.  Return a[maj_index]

Above algorithm loops through each character and maintains a count of a[maj_index]. If the next character is same then increment the count, if the next character is not same then decrement the count, and if the count reaches 0 then changes the maj_index to the current character and set the count again to 1. So, the first phase of the algorithm gives us a candidate character .

In the second phase we need to check if the candidate is really a superior character . Second phase is simple and can be easily done in O(n). We just need to check if count of the candidate character is greater than n/2.

Example :

Let the string be str = aa@vaag

• Initialize maj_index = 0, count = 1
• Next character is a, which is same as a[maj_index] => count = 2
• Next character is @, which is different from a[maj_index] => count = 1
• Next character is v, which is different from a[maj_index] => count = 0Since count = 0, change candidate for majority character to v => maj_index = 3, count = 1
• Next character is a, which is different from a[maj_index] => count = 0Since count = 0, change candidate for majority character to a => maj_index = 4
• Next character is a, which is same as a[maj_index] => count = 2
• Next character is g, which is different from a[maj_index] => count = 1
• Finally candidate for majority character is a.

First step uses Moore’s Voting Algorithm to get a candidate for superior character .

2. Check if the character obtained in step 1 is superior element or not :

printMajority (str, size)
1.  Find the candidate for majority
2.  If candidate is majority. i.e., appears more than n/2 times.
       Print the candidate
3.  Else
       Print "No Superior Character "

Implementation :

/* C++ Program for finding out  
   Superior character in a string */
#include <bits/stdc++.h> 
using namespace std; 
  
/* Function to find the candidate for Majority */
char findCandidate(string str, int size) 
{ 
    int maj_index = 0, count = 1; 
    for (int i = 1; i < size; i++) 
    { 
        if (str[maj_index] == str[i]) 
            count++; 
        else
            count--; 
        if (count == 0) 
        { 
            maj_index = i; 
            count = 1; 
        } 
    } 
    return str[maj_index]; 
} 
  
/* Function to check if the candidate 
   occurs more than n/2 times */
bool isSuperior(string str, int size, char cand) 
{ 
    int count = 0; 
    for (int i = 0; i < size; i++) 
      
    if (str[i] == cand) 
    count++; 
          
    if (count > size/2) 
    return 1; 
      
    else
    return 0; 
} 
  
/* Function to print Superior Character */
void printSuperior(string str, int size) 
{ 
   /* Find the candidate for Superior*/
   char cand = findCandidate(str, size); 
  
   /* Print the candidate if it is Superior*/
   if (isSuperior(str, size, cand)) 
   cout << " " << cand << " "; 
     
   else
   cout << "No Superior Character"; 
} 
  
  
/* Driver function to test above functions */
int main() 
{ 
	string str = "a#aafaa$56aaBaha0a3";
    int size = str.size(); 
      
    // Function calling 
    printSuperior(str, size); 
      
    return 0; 
} 

a

Time Complexity : O(n) 
Space Complexity : O(1)