Find Majority of Elements in a String using PHP

Let’s imagine that we have a string with an arbitrary number of characters. Each character in the string represents a vote for a specific class. We want to find the class that has the majority vote. This means any character which makes up more than 50% of the string. However, the challenge is to do this in linear time and constant space. So we want to achieve O(n) in both time and space complexity.

We can achieve this using the Boyer–Moore majority vote algorithm. Here’s a simple implementation of this algorithm in PHP.

<?php

function majorityElement(String $input) {
    $count = $candidate = 0;
    $length = strlen($input);
    
    for ($i = 0; $i < $length; $i++) {
        if ($count == 0) {
            $candidate = $input[$i];
            $count = 1;
            continue;
        } elseif ($candidate == $input[$i]) {
            $count++;
        } else {
            $count--;
        }
    }
    
    if ($count == 0) {
        return false;
    } else {
        $count = 0;
        for ($i = 0; $i < $length; $i++) {
            if ($candidate == $input[$i]) {
                $count++;
            }
        }
        
        if ($count > intdiv($length, 2)) {
            return $candidate;
        }
    }

    return false;
}

So given the string "ACBCDCECFCCGCCCH" this function would return "C" since this character appears more than 50% of the time throughout the string. There are a total of 16 characters in the string and the character "C" appears exactly 9 times, which constitutes 56.25% of the length of the string (9 / 16 = 0.5625). The function will return false if no majority is found.

Some practical applications of this algorithm exist in pattern recognition, binary search trees, and many distributed systems where consensus is required among peers of the system.