| 28 March 2025 | Challenge 314 |
Monotonous Prefixes
Task 1: Equal Strings
Submitted by: Mohammad Sajid Anwar
You are given three strings.
You are allowed to remove the rightmost character of a string to make all equals.
Write a script to return the number of operations to make it equal otherwise -1.
Example 1
Input: $s1 = "abc", $s2 = "abb", $s3 = "ab"
Output: 2
Operation 1: Delete "c" from the string "abc"
Operation 2: Delete "b" from the string "abb"
Example 2
Input: $s1 = "ayz", $s2 = "cyz", $s3 = "xyz"
Output: -1
Example 3
Input: $s1 = "yza", $s2 = "yzb", $s3 = "yzc"
Output: 3
Solution
First of all I’d like to generalize this task to an arbitrary number of strings.
The task may be reformulated as finding the longest common prefix of all given strings as we have to delete all characters beyond this common prefix.
The longest common prefix may be found with a single regex.
To this end we join the strings with a character not contained in any of the strings.
For simplicity this will be the newline character "\n" in the following, which will not be matched by the dot metacharacter.
To find the longest common prefix, we capture a non-empty prefix from the first string ^(.*) and move forward unconditionally up to (but not including) the next newline .*+.
Then we try to match a newline and the prefix from the first string.
Again, we move forward unconditionally up to the next newline or end-of-string \n\1.*+.
This second part must match for all but the first string, i.e. with a repetition factor of $#_ and consume the rest of the joined strings, resulting in (?:...){$#_}$.
Having found the length of the common prefix, we find the number of to-be-deleted characters from the length of the joined strings and the number of given strings.
use strict;
use warnings;
sub equal_strings {
my $str = join "\n", @_;
$str =~ /^(.+).*+(?:\n\1.*+){$#_}$/ or return -1;
length($str) - (1 + length $1) * @_ + 1;
}
See the full solution to task 1.
Task 2: Sort Column
Submitted by: Mohammad Sajid Anwar
You are given a list of strings of same length.
Write a script to make each column sorted lexicographically by deleting any non sorted columns.
Return the total columns deleted.
Example 1
Input: @list = ("swpc", "tyad", "azbe")
Output: 2
swpc
tyad
azbe
Column 1: "s", "t", "a" => non sorted
Column 2: "w", "y", "z" => sorted
Column 3: "p", "a", "b" => non sorted
Column 4: "c", "d", "e" => sorted
Total columns to delete to make it sorted lexicographically.
Example 2
Input: @list = ("cba", "daf", "ghi")
Output: 1
Example 3
Input: @list = ("a", "b", "c")
Output: 0
Solution
We build a matrix from the characters of the given strings. Then we check if the columns are monotonously increasing. If there is a descent, the column needs to be removed.
Strings having different lengths are permitted here. Missing values must come first in a sorted column.
use strict;
use warnings;
use PDL;
use PDL::Char;
use PDL::NiceSlice;
sub sort_column {
my $m = PDL::Char->new(@_)->long->xchg(0, 1);
sum orover $m(1:-1) < $m(0:-2);
}
See the full solution to task 2.
If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.