The weekly challenge 372 - Task 2: Largest Substring

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-372/#TASK2
 3 #
 4 # Task 2: Largest Substring
 5 # =========================
 6 #
 7 # You are given a string.
 8 #
 9 # Write a script to return the length of the largest substring between two
10 # equal characters excluding the two characters. Return -1 if there is no such
11 # substring.
12 #
13 ## Example 1
14 ##
15 ## Input: $str = "aaaaa"
16 ## Output: 3
17 ##
18 ## For character "a", we have substring "aaa".
19 #
20 ## Example 2
21 ##
22 ## Input: $str = "abcdeba"
23 ## Output: 5
24 ##
25 ## For character "a", we have substring "bcdeb".
26 #
27 ## Example 3
28 ##
29 ## Input: $str = "abbc"
30 ## Output: 0
31 ##
32 ## For character "b", we have substring "".
33 #
34 ## Example 4
35 ##
36 ## Input: $str = "abcaacbc"
37 ## Output: 4
38 ##
39 ## For character "a", we have substring "bca".
40 ## For character "b", we have substring "caac".
41 #
42 ## For character "c", we have substring "aacb".
43 #
44 ## Example 5
45 ##
46 ## Input: $str = "laptop"
47 ## Output: 2
48 ##
49 ## For character "p", we have substring "to".
50 #
51 ############################################################
52 ##
53 ## discussion
54 ##
55 ############################################################
56 #
57 # For each character in $str, we collect all of its positions. In the end,
58 # we can calculate the largest substring for each specific character by subtracting
59 # the index of the first such character from the index of the last one, and removing
60 # one more. Out of all of these numbers, we just need to keep the maximum value.
61 
62 use v5.36;
63 
64 largest_substring("aaaaa");
65 largest_substring("abcdeba");
66 largest_substring("abbc");
67 largest_substring("abcaacbc");
68 largest_substring("laptop");
69 largest_substring("abc");
70 
71 sub largest_substring($str) {
72     say "Input: \"$str\"";
73     my @chars = split //, $str;
74     my $char_positions;
75     foreach my $i (0..$#chars) {
76         push @{$char_positions->{$chars[$i]}}, $i;
77     }
78     my $max = -1;
79     foreach my $char (keys %$char_positions) {
80         my @tmp = @{ $char_positions->{$char} };
81         my $diff = $tmp[-1] - $tmp[0] - 1;
82         $max = $diff if $diff > $max;
83     }
84     say "Output: $max";
85 }