Task 1: Make Palindrome
You are given a string. Write a script to convert the given string to a palindrome by adding characters in front of it.
Example Output
Input: $str = "pinnipeds"
Output: "sdepinnipeds"
Input: $str = "abcd"
Output: "dcbabcd"
Input: $str = "bananas"
Output: "sananabananas"
Logic
To obtain the shortest palindrome by prepending characters, we need to find the longest prefix of the string that is already a palindrome. Once the longest palindromic prefix of length L is identified, the remaining suffix from index L onwards is reversed and prepended to the original string.
Perl Solution
ch-1.pl
sub make_palindrome ($str) {
return $str if length($str) <= 1;
my $n = length($str);
for my $len ( reverse 1 .. $n ) {
my $prefix = substr( $str, 0, $len );
if ( $prefix eq reverse($prefix) ) {
my $suffix_to_add = substr( $str, $len );
return reverse($suffix_to_add) . $str;
}
}
return reverse( substr( $str, 1 ) ) . $str;
}
Python Solution
ch-1.py
def make_palindrome(s: str) -> str:
"""Convert given string to shortest palindrome by prepending characters."""
if len(s) <= 1:
return s
n = len(s)
for length in range(n, 0, -1):
prefix = s[:length]
if prefix == prefix[::-1]:
suffix_to_add = s[length:]
return suffix_to_add[::-1] + s
return s[1:][::-1] + s
Task 2: Maximum Product of Word Lengths
You are given an array of strings. Write a script to return the maximum value of len($words[i]) * len($words[j]) where the two words do not share any common letters. If no such two words exist, return 0.
Example Output
Input: @words = ("a", "ab", "abc", "d", "de", "def")
Output: 9 ("abc" and "def")
Input: @words = ("meet", "app", "code", "sky", "bold")
Output: 16 ("meet" and "bold")
Logic
Each word consists of lowercase letters 'a'..'z'. We represent the set of characters in each word as a 26-bit integer mask, where the k-th bit is set if the k-th letter is present. Two words share no common letters if and only if their bitwise AND is zero: (mask[i] & mask[j]) == 0. This allows checking disjointness in O(1) time per pair.
Perl Solution
ch-2.pl
sub max_product (@words) {
return 0 if @words < 2;
my @masks;
my @lengths;
for my $w (@words) {
my $mask = 0;
for my $char ( split //, lc($w) ) {
$mask |= ( 1 << ( ord($char) - ord('a') ) );
}
push @masks, $mask;
push @lengths, length($w);
}
my $max_prod = 0;
my $n = scalar @words;
for my $i ( 0 .. $n - 2 ) {
for my $j ( $i + 1 .. $n - 1 ) {
if ( ( $masks[$i] & $masks[$j] ) == 0 ) {
my $prod = $lengths[$i] * $lengths[$j];
$max_prod = $prod if $prod > $max_prod;
}
}
}
return $max_prod;
}
Python Solution
ch-2.py
def max_product(words: list[str]) -> int:
"""Return maximum len(words[i]) * len(words[j]) without common letters."""
if len(words) < 2:
return 0
masks: list[int] = []
lengths: list[int] = []
for w in words:
mask = 0
for char in w.lower():
mask |= 1 << (ord(char) - ord("a"))
masks.append(mask)
lengths.append(len(w))
max_prod = 0
n = len(words)
for i in range(n - 1):
for j in range(i + 1, n):
if (masks[i] & masks[j]) == 0:
prod = lengths[i] * lengths[j]
if prod > max_prod:
max_prod = prod
return max_prod