The Weekly Challenge 264

Greatest English Letter & Target Array: Dual-Case Character Discovery and Dynamic Index Splicing in Perl & Python

Lubos Kolouch April 8, 2024 Challenge Details GitHub Solutions

Task 1: Greatest English Letter

You are given a string, $str, made up of only alphabetic characters [a..zA..Z].

Write a script to return the greatest English letter in the given string.

A letter is greatest if it occurs as both lower and upper case. Also letter 'b' is greater than 'a' if 'b' appears after 'a' in the English alphabet. If no such letter exists, return an empty string.

Example 1: Input: $str = 'PeRlwEeKLy' → Output: 'L'

Example 2: Input: $str = 'ChaLlenge' → Output: 'L'

Example 3: Input: $str = 'The' → Output: ''

Method Explanation

The problem asks for the lexicographically largest letter in the English alphabet that appears in the input string in both lowercase and uppercase forms.

Our approach separates character observations by case:

  1. Scan the input string and record which letters appear in lowercase and which appear in uppercase.
  2. Compute the intersection of both sets of letters (normalized to lowercase).
  3. If the intersection is non-empty, find the maximum letter alphabetically and return its uppercase representation; otherwise return an empty string ''.

This runs in $O(N)$ time where $N$ is the length of the string, and $O(1)$ space since the alphabet has at most 26 letters.

Perl Solution

use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(Str);

signature_for greatest_english_letter => (
    method     => 0,
    positional => [Str],
);

sub greatest_english_letter ($str) {
    my %seen;

    for my $char ( split //, $str ) {
        if ( $char =~ /^[A-Z]$/ ) {
            $seen{ lc $char }{upper} = 1;
        }
        elsif ( $char =~ /^[a-z]$/ ) {
            $seen{ lc $char }{lower} = 1;
        }
    }

    my $greatest_letter = '';
    for my $letter ( keys %seen ) {
        if ( $seen{$letter}{upper} && $seen{$letter}{lower} ) {
            $greatest_letter = $letter if $letter gt $greatest_letter;
        }
    }

    return uc $greatest_letter;
}

Python Solution

def greatest_english_letter(s: str) -> str:
    """Return the greatest English letter occurring in both lower and upper case."""
    lower_set = {c.lower() for c in s if c.islower()}
    upper_set = {c.lower() for c in s if c.isupper()}

    common_letters = lower_set & upper_set
    greatest_letter = max(common_letters, default="")
    return greatest_letter.upper()

Task 2: Target Array

You are given two arrays of integers, @source and @indices. The @indices can only contain integers 0 ≤ i < size of @source.

Write a script to create a target array by inserting at index $indices[$i] the value $source[$i].

Example 1: Input: @source = (0, 1, 2, 3, 4), @indices = (0, 1, 2, 2, 1) → Output: (0, 4, 1, 3, 2)

Example 2: Input: @source = (1, 2, 3, 4, 0), @indices = (0, 1, 2, 3, 0) → Output: (0, 1, 2, 3, 4)

Example 3: Input: @source = (1), @indices = (0) → Output: (1)

Method Explanation

We start with an empty target array and iterate over pairs of (source[i], indices[i]) in lockstep:

  1. In Perl, we use splice(@target, $indices->[$i], 0, $source->[$i]), which inserts $source->[$i] at position $indices->[$i] while shifting subsequent elements to the right.
  2. In Python, we iterate over zip(source, indices) and call target.insert(idx, s).

Each insertion into an array of length $k$ takes $O(k)$ time in the worst case, resulting in $O(N^2)$ total time complexity and $O(N)$ space for the output array of size $N$.

Perl Solution

use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Int);

signature_for create_target_array => (
    method     => 0,
    positional => [ ArrayRef [Int], ArrayRef [Int] ],
);

sub create_target_array ( $source, $indices ) {
    my @target;

    for my $i ( 0 .. $#$source ) {
        splice( @target, $indices->[$i], 0, $source->[$i] );
    }

    return \@target;
}

Python Solution

def create_target_array(source: list[int], indices: list[int]) -> list[int]:
    """Create target array by inserting source[i] at index indices[i]."""
    target: list[int] = []
    for s, idx in zip(source, indices):
        target.insert(idx, s)
    return target