The Weekly Challenge #394

Task 1: Alternate Case

Method Explanation

An alternating case string of length $N$ (where uppercase count equals lowercase count, so $N = 2K$) has only two valid target configurations:

• Pattern A (Uppercase first): Uppercase letters at even indices $(0, 2, 4, \dots, 2K - 2)$ and lowercase letters at odd indices $(1, 3, 5, \dots, 2K - 1)$.
• Pattern B (Lowercase first): Lowercase letters at even indices $(0, 2, 4, \dots, 2K - 2)$ and uppercase letters at odd indices $(1, 3, 5, \dots, 2K - 1)$.

A well-known property of adjacent swaps is that swapping elements into their target positions preserves their relative order when minimizing inversions. That is, the $k$-th uppercase character from the left should map directly to the $k$-th uppercase position in the target pattern.

Furthermore, moving an uppercase character to its target slot automatically displaces the corresponding lowercase characters into their proper slots. Therefore, the minimum number of adjacent swaps required to achieve a pattern is simply: $$\sum_{k=0}^{K-1} |\text{pos}_k - \text{target\_pos}_k|$$ We compute this sum for both possible patterns (Uppercase first vs. Lowercase first) and return the minimum of the two.

Perl Implementation

sub min_swaps_to_alternate ($str) {
    ($str) = $STR_CHECK->($str);

    my @chars = split //, $str;
    my $n     = scalar @chars;
    return 0 if $n <= 1;

    my ( @upper_pos, @lower_pos );
    for my $i ( 0 .. $#chars ) {
        my $c = $chars[$i];
        if ( $c =~ /^[A-Z]\z/ ) {
            push @upper_pos, $i;
        }
        elsif ( $c =~ /^[a-z]\z/ ) {
            push @lower_pos, $i;
        }
        else {
            die "String must contain only English alphabetic letters: $c";
        }
    }

    die 'String must contain equal number of uppercase and lowercase letters'
      if @upper_pos != @lower_pos;

    # Pattern A: Upper at even indices (0, 2, 4...), Lower at odd indices (1, 3, 5...)
    my $swaps_upper_first = 0;
    for my $k ( 0 .. $#upper_pos ) {
        $swaps_upper_first += abs( $upper_pos[$k] - ( 2 * $k ) );
    }

    # Pattern B: Lower at even indices (0, 2, 4...), Upper at odd indices (1, 3, 5...)
    my $swaps_lower_first = 0;
    for my $k ( 0 .. $#lower_pos ) {
        $swaps_lower_first += abs( $lower_pos[$k] - ( 2 * $k ) );
    }

    return min( $swaps_upper_first, $swaps_lower_first );
}

Python Implementation

def min_swaps_to_alternate(s: str) -> int:
    """Calculate minimum adjacent swaps to turn string into alternating case."""
    if len(s) <= 1:
        return 0

    upper_pos: list[int] = []
    lower_pos: list[int] = []

    for idx, char in enumerate(s):
        if char.isupper():
            upper_pos.append(idx)
        elif char.islower():
            lower_pos.append(idx)
        else:
            raise ValueError(f"String must contain only English letters: {char}")

    if len(upper_pos) != len(lower_pos):
        raise ValueError("String must contain equal number of uppercase and lowercase letters")

    # Pattern A: Upper at even indices (0, 2, 4...), Lower at odd (1, 3, 5...)
    swaps_upper_first = sum(abs(pos - 2 * k) for k, pos in enumerate(upper_pos))

    # Pattern B: Lower at even indices (0, 2, 4...), Upper at odd (1, 3, 5...)
    swaps_lower_first = sum(abs(pos - 2 * k) for k, pos in enumerate(lower_pos))

    return min(swaps_upper_first, swaps_lower_first)

Task 2: Alternating Vowels Consonants

Method Explanation

To solve this task:

1. We inspect the first string s1 and generate all contiguous substrings that strictly alternate between vowels (a, e, i, o, u) and consonants. Note that if a candidate violates the alternating rule when adding the next character, extending it further from the current starting index will also violate the alternating property, allowing an early break.
2. For each valid alternating substring, we verify if it is contained in both s2 and s3 (e.g. via index in Perl or in in Python).
3. We keep track of the maximum length among all valid candidates common to all three strings.
4. Finally, we gather all candidates matching this maximum length, preserving their order of first appearance without duplicates.

Perl Implementation

sub is_vowel ($c) {
    return $c =~ /^[aeiouAEIOU]\z/ ? 1 : 0;
}

sub is_alternating ($sub) {
    return 0 if length($sub) == 0;
    my @chars = split //, $sub;
    for my $i ( 1 .. $#chars ) {
        return 0 if is_vowel( $chars[$i] ) == is_vowel( $chars[ $i - 1 ] );
    }
    return 1;
}

sub longest_alternating_common_substrings ($strs) {
    ($strs) = $STRS_CHECK->($strs);
    die 'Exactly three strings are required' if @$strs != 3;

    my ( $s1, $s2, $s3 ) = @$strs;
    my $len1 = length($s1);

    my %valid_candidates;

    for my $i ( 0 .. $len1 - 1 ) {
        for my $len ( 1 .. $len1 - $i ) {
            my $candidate = substr( $s1, $i, $len );
            if ( !is_alternating($candidate) ) {
                last;
            }
            if ( index( $s2, $candidate ) != -1 && index( $s3, $candidate ) != -1 ) {
                $valid_candidates{$candidate} = length($candidate);
            }
        }
    }

    return () if !%valid_candidates;

    my $max_len = 0;
    for my $len ( values %valid_candidates ) {
        $max_len = $len if $len > $max_len;
    }

    # Extract all candidates of max_len in order of first appearance in s1
    my @result;
    my %seen;
    for my $i ( 0 .. $len1 - $max_len ) {
        my $sub = substr( $s1, $i, $max_len );
        if ( exists $valid_candidates{$sub} && $valid_candidates{$sub} == $max_len && !$seen{$sub} ) {
            push @result, $sub;
            $seen{$sub} = 1;
        }
    }

    return @result;
}

Python Implementation

def is_vowel(c: str) -> bool:
    """Return True if character is an English vowel, False otherwise."""
    return c.lower() in {"a", "e", "i", "o", "u"}


def is_alternating(sub: str) -> bool:
    """Return True if string strictly alternates between vowels and consonants."""
    if not sub:
        return False
    return all(is_vowel(sub[i]) != is_vowel(sub[i - 1]) for i in range(1, len(sub)))


def longest_alternating_common_substrings(strs: Sequence[str]) -> list[str]:
    """Find all longest contiguous alternating substrings common to all three strings."""
    if len(strs) != 3:
        raise ValueError("Exactly three strings are required")

    s1, s2, s3 = strs
    len1 = len(s1)
    valid_candidates: dict[str, int] = {}

    for i in range(len1):
        for length in range(1, len1 - i + 1):
            candidate = s1[i : i + length]
            if not is_alternating(candidate):
                break
            if candidate in s2 and candidate in s3:
                valid_candidates[candidate] = len(candidate)

    if not valid_candidates:
        return []

    max_len = max(valid_candidates.values())
    result: list[str] = []
    seen: set[str] = set()

    for i in range(len1 - max_len + 1):
        sub = s1[i : i + max_len]
        if sub in valid_candidates and valid_candidates[sub] == max_len and sub not in seen:
            result.append(sub)
            seen.add(sub)

    return result