Task — Good substrings

You are given a string. Write a script to return the number of good substrings of length three in the given string. A string is good if there are no repeated characters.

Examples

Example 1
Input: $str = 'abcaefg'
Output: 5
Good substrings of length 3: abc, bca, cae, aef and efg

Example 2
Input: $str = 'xyzzabc'
Output: 3
Good substrings of length 3: 'xyz', 'zab' and 'abc'

Example 3
Input: $str = 'aababc'
Output: 1
Good substrings of length 3: 'abc'

Example 4
Input: $str = 'qwerty'
Output: 4
Good substrings of length 3: 'qwe', 'wer', 'ert' and 'rty'

Example 5
Input: $str = 'zzzaaa'
Output: 0

Analysis

This time I have gone for efficiency and looked for a solution that never repeats a comparison. For example, if the string is αβγδ, the obvious solution is to test α ne β and α ne γ and β ne γ and then move on to β ne γ and β ne δ and γ ne δ.

Note that we have therefore calculated β ne γ twice. In any sensible scenario that is unlikely to matter, but I have saved a few microseconds by coming up with a solution that avoids repeating any comparison.

The essence of this is that we first compare β and γ. If these are the same we know that the triplets starting at α and the one starting at β are bad, and we can move on to looking at the triplet starting at γ.

Otherwise we check whether α and β differ, and if they do, whether α and γ differ, and if these are both true we have a good substring.

This algorithm never repeats a comparison and, I believe, never performs an unnecessary comparison.

Lastly, I start my solution by converting the string into an array. I did that because $chars[$p] is easier to read than substr($chars, $p, 1). Past experiments have shown that there is negligible difference in performance between these two approaches.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2025-12-01
use utf8;     # Week 350 - task 1 - Good substrings
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

good_substrings('abcaefg');
good_substrings('xyzzabc');
good_substrings('aababc');
good_substrings('qwerty');
good_substrings('zzzaaa');

sub good_substrings {
    
    my (@chars, $p, $good, $explain);
    
    # initialise
    @chars = split('', $_[0]);
    
    # loop over chars
    $p = 0;
    while ($p < @chars - 2) {
        
        # skip forward 2 if these two match
        if ($chars[$p + 1] eq $chars[$p + 2]) {
            $p ++;

        # result!
        } elsif ($chars[$p] ne $chars[$p + 1] and $chars[$p] ne $chars[$p + 2]) { 
            $good ++;
            $explain .= qq['$chars[$p]$chars[$p + 1]$chars[$p + 2]', ];
        }
        $p ++;
    }
    
    say qq[\nInput:  '$_[0]'];
    say qq[Output: ] . ($good ? qq[$good - ] . substr($explain, 0, -2) : 0);
}

Output

Input:  'abcaefg'
Output: 5 - 'abc', 'bca', 'cae', 'aef', 'efg'

Input:  'xyzzabc'
Output: 3 - 'xyz', 'zab', 'abc'

Input:  'aababc'
Output: 1 - 'abc'

Input:  'qwerty'
Output: 4 - 'qwe', 'wer', 'ert', 'rty'

Input:  'zzzaaa'
Output: 0