Replace Characters Algorithm with O(n) Time/Complexity Notation

[rwhite35]

Reading a CompSci book and it gives problems requiring algorithms WITHOUT the use of (lang.) build in function.  In the following problem, the process should remove characters in a string using a set of target characters.  It should be able to do this in one pass - or O(n).  According to the book, there is a solution - though I'm skeptical and the book is using Java.

 

The following function employs PHP built in functions and works as required, in one pass.  

function removeWithBuiltin($string,$chr,$replacement) {
    foreach($chr as $v) { // O(1)
	$part = $v."|";
	$pattern = $pattern . $part; // example a|k|e|x
    }
    $pattern = rtrim( $pattern, "|" ); //trim off last vertical bar
    $pattern = "/".$pattern."/";
    $string = preg_filter($pattern, $replacement, $string); // O(1)
    var_dump($string);
} 

The following class is functionally the same as the above.  It returns the same string as removeWithBuiltin().

class stringEditor {
    public $inputStr;   // string to edit
    public $newStr;   // string to return
    public $rmSet;   // array, unknown set of characters to remove
	
    public function __construct($str,$rArr) {
	$this->inputStr = $str;
	$this->rmSet = $rArr;
    }
/*
* removeChar loops through input array and compares each remove target character to its value, 
* if value and target are equal, assign null to buffer; else assign value to buffer
* return array $buffer, processed input characters minus this removed character target (if any)
*/
    protected function removeChar($strArr,$chr) {
	$buffer = array();
	$cnt = count($strArr);
		
	for( $i=0; $i<$cnt; $i++ ) { // eval each character, highest term O($i)
	    $buffer[$i] = ( $strArr[$i] == $chr ) ? null : $strArr[$i];
	}
	    if(!empty($buffer)) { return $buffer; } else { return $strArr; }
	}
/*
* converts input string to indexed array and calls an instance of 
* removeChar with string array and each character to search and replace with null value
* return string $editString, input string without removed characters
*/
    public function processString() {
	$strArray = str_split($this->inputStr); // convert string to array of chars
	
        foreach ($this->rmSet as $char) { // eval each character in the remove set
	    $e=0;
	    if (empty($this->newStr)) { // initial condition, $this->newStr doesnt exist
	        $this->newStr[] = $this->removeChar($strArray, $char);
	    } else { // now use previous and call removeChar, overloading 0 with each loop
	        $this->newStr[0]= $this->removeChar($this->newStr[$e], $char);
	        $e++;
	    }
        }
/* 
* flatten $this->newStr array object in to a string 
* prototype: array([0]=>array([0]=>char, [1]=>char, ... ))
*/
        $array = $this->newStr[0]; // overloaded all previous edits
        for($i=0; $i<count($array); $i++) {
            $editString = $editString . $array[$i];
	}
		
	if(isset($editString) && !empty($editString)) {return $editString;} else {return false;}
   }

}  // close class 

This class takes "n" number of characters to remove characters from a given string "t" characters long.  So its notation should be O(log n^t); or possible O(n * t), but not O(n).  

 

And finally, here is the questions:

Any thoughts on how this class could be modified to only loop over the input string - once - removing an unspecified set of characters?  

 

Here is the test parameters:

$randomString = "bucked the science from popular";
$chars = [ "a", "k", "e", "x" ];

$removeObj = new stringEditor( $randomString, $chars );
$results = $removeObj->processString();

echo $results; // outputs  bucd th scinc from populr

Some direction on how to improve the performance of the class would be appreciated.

Edited July 8, 2015 by rwhite35

[requinix]

I don't know of an O(n) solution. The "normal" solution would be O(n*m) and a slightly better one would be O(n*log m).

$string = preg_filter($pattern, $replacement, $string); // O(1)

It's not actually O(1) since you have to consider what that function is doing: loop through the inputs (n) and test the pattern, where the pattern is a set of alternations (m). Thus that's O(n*m), but will be faster than your PHP since it's compiled code. However efficiency isn't determined by runtime but by complexity.

 

The normal solution is like

output = ""
for each character in input { // O(n)
	if character is not found in search string { // O(m)
		output += character
	}
}
// O(n*m)

The faster solution is

sort the search string // O(log m)

output = ""
for each character in input { // O(n)
	if character is not found in search string using a binary search { // O(log m)
		output += character
	}
}
// O(n*log m)

[rwhite35]

Thanks for the feedback.  I'll work in the direction of your second pseudocode ( O(log m) ).  That seems more intuitive then what I was proposing.  Appreciate the feedback, that's a big help.

[gizmola]

Perhaps what they were actually looking for is your implementation of the search.

[rwhite35]

Perhaps what they were actually looking for is your implementation of the search.

 

Yes that could be the case.  I don't think there is a right or wrong answer per se' and I'm really doing this for my own "enjoyment" and education.  But yes, some sort of search mechanism could potentially be another solution.  The book is the Wrox Programmer to Programmer series and titled Programming Interviews Exposed. It doesn't really give any hard solution to the problems it poses, just boundaries and general direction.  

[requinix]

The book is the Wrox Programmer to Programmer series and titled Programming Interviews Exposed.

I don't know where you are in the book, but the errata (3rd edition) mentions an instance of O(n) on page 26 that's supposed to be O(n^2).

[gizmola]

Seems like the mystery is solved.  Nice thread guys!