RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved various sorts of string mangling. (Note that this ends today.)

Task 1: Rearrange Spaces

You are given a string text of words that are placed among number of spaces.

Write a script to rearrange the spaces so that there is an equal number of spaces between every pair of adjacent words and that number is maximised. If you can't distribute, place the extra spaces at the end. Finally return the string.

This seems quite fiddly, but it falls into steps.

• Split the words into a list, and count the spaces.

• Work out the number of spaces per division, and the remainder.

• Join the words by the number of spaces per division, and then add the remainder onto the end.

Thus in Ruby:

def rearrangespaces(a)
  words = []
  spaces = 0
  ww = ""

Rather than use the built-in split, which would lose some information I need, I'll look through the input one character at a time.

  a.chars.each do |c|

If it's a space, increment the space count.

    if c == ' '
      spaces += 1

And if there was a word in progress, add it to the list and clear the word in progress.

      if ww != ""
        words.push(ww)
        ww = ""
      end

Otherwise, add a character to the word in progress.

    else
      ww += c
    end
  end

If we ended with a word in progress, push that on too.

  if ww != ""
    words.push(ww)
  end

If there aren't any divisions, all the spaces will go in the remainder.

  spdiv = 0
  remainder = spaces

Count the number of divisions to see if we can do better.

  divs = words.size - 1

If we have any, allocate the spaces as evenly as we can, and put the rest in the remainder.

  if divs > 0
    spdiv, remainder = spaces.divmod(divs)
  end

Build the joined list of words.

  out = words.join(" " * spdiv)

Add the remainder if any.

  if remainder > 0
    out += " " * remainder
  end
  out
end

Task 2: Largest Substring

You are given a string.

Write a script to return the length of the largest substring between two equal characters excluding the two characters. Return -1 if there is no such substring.

It doesn't actually matter what's in the substring, only how long it is.

So what I actually want is the maximum distance between a pair of identical characters.

Obviously I'll have to search all possible pairs of start and end points, which is going to be O(N²). But if I search the most-separated pairs first, I can potentially cut things short and just return with the first match I find, because that will have the maximum distance that's present.

Thus in Perl:

sub largestsubstring($a) {

Get a list of characters, for convenient indexing.

  my @cc = split '',$a;

Start with the longest possible inter-character gap and decrement until we get a match.

  foreach my $offset (reverse(1 .. $#cc)) {

Try each starting point that will have another character offset characters later.

    foreach my $x (0 .. $#cc - $offset) {

If there's a match, return that length immediately.

      if ($cc[$x] eq $cc[$x + $offset]) {
        return $offset - 1;
      }
    }
  }

If we get to the end with no match (which none of the examples does), return -1.

  -1;
}

Full code on codeberg.