The Weekly Challenge 018

Longest Common Substring and Priority Queue

Solutions on GitHub

Task 1: Longest Common Substring

Write a script that takes 2 or more strings as command line parameters and prints the longest common substring.

Example

Input: "ABABC", "BABCA", "ABCBA" Output: Common string ABC

Logic

Generate all possible substrings of the first string. For each subsequent string, filter our list of candidate substrings to keep only those that are present. Sort the remaining common substrings by length in descending order, and return the longest one.

Perl Solution

ch-1.pl

my %all_strings; my $seen_first; sub insert_to_all_strings { my $str = shift; my %seen_str; my $length = length($str); for my $pos ( 0 .. $length - 1 ) { for my $length_remain ( 1 .. $length - $pos ) { my $sub_string = substr( $str, $pos, $length_remain ); next if $seen_first and not defined $all_strings{length($sub_string)}{$sub_string}; next if $seen_str{$sub_string}; $seen_str{$sub_string} = 1; $all_strings{ length($sub_string) }{$sub_string}++; } } $seen_first = 1; } sub longest_str { my @strings = @_; my $found_solution; insert_to_all_strings($_) for (@strings); foreach my $str_length ( sort { $b <=> $a } keys %all_strings ) { foreach my $string ( keys %{ $all_strings{$str_length} } ) { if ( $all_strings{$str_length}{$string} == scalar @strings ) { say "Common string $string"; $found_solution = $string; } } last if $found_solution; } return $found_solution; }

Python Solution

ch-1.py

def longest_common_substring(strings: list[str]) -> str: if not strings: return "" # Generate all substrings of the first string first = strings[0] n = len(first) candidates = set() for i in range(n): for j in range(i + 1, n + 1): candidates.add(first[i:j]) # Keep only those present in all other strings for s in strings[1:]: candidates = {cand for cand in candidates if cand in s} if not candidates: return "" return max(candidates, key=len)

Task 2: Priority Queue

Implement a Priority Queue. It should support:

  1. is_empty: Check if the queue is empty.
  2. insert_with_priority: Add an element with an associated priority.
  3. pull_highest_priority_element: Remove and return the element with the highest priority (FIFO for ties).

Logic

We use a hash table (or dictionary) where the keys are priorities and the values are array references (or lists) storing elements of that priority. Since elements with the same priority are added to the end of the array, pulling using shift (or pop/dequeue from the front) naturally respects FIFO order for ties.

Perl Solution

ch-2.pl

sub is_empty { my $hash_ref = shift; return %{$hash_ref} ? 0 : 1; } sub insert_with_priority { my ( $hash_ref, $priority, $element ) = @_; my %queue = %{$hash_ref}; push @{ $queue{$priority} }, $element; return %queue; } sub pull_highest_priority_element { my $hash_ref = shift; foreach my $priority ( sort { $b <=> $a } keys %$hash_ref ) { my $element = shift @{ %${hash_ref}{$priority} }; delete $$hash_ref{$priority} unless scalar @{ %${hash_ref}{$priority} }; return $element; } return 1; }

Python Solution

ch-2.py

class PriorityQueue: def __init__(self): self.queue = {} def is_empty(self) -> bool: return len(self.queue) == 0 def insert_with_priority(self, priority: int, element: str): if priority not in self.queue: self.queue[priority] = [] self.queue[priority].append(element) def pull_highest_priority_element(self) -> str: if self.is_empty(): raise IndexError("Queue is empty") highest = max(self.queue.keys()) element = self.queue[highest].pop(0) if not self.queue[highest]: del self.queue[highest] return element