Expressive Words: Run-Length Encoding

[!NOTE] This module explores the core principles of Expressive Words: Run-Length Encoding, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Problem Definition

Sometimes people repeat letters to represent extra feeling. For example:

• "hello" → "heeellooo"
• "hi" → "hiiii"

In strings like "heeellooo", we have groups of adjacent letters that are all the same: "h", "eee", "ll", "ooo".

You are given a string s and an array of query strings words. A query word is stretchy if it can be made to be equal to s by any number of applications of the following extension operation: choose a group consisting of characters c, and add some number of characters c to the group so that the size of the group is three or more.

Return the number of query strings that are stretchy.

Example 1:

Input: s = "heeellooo", words = ["hello", "hi", "helo"]
Output: 1
Explanation:
We can extend "e" and "o" in the word "hello" to get "heeellooo".
We can't extend "helo" to get "heeellooo" because the group "ll" is not size 3 or more.

---

2. Interactive Analysis

Watch how the RLE algorithm matches the raw “Barcode” sequences.

Target String `s`: Query String `w`:

Target RLE

Query RLE

Click 'Compare RLE' to evaluate.

---

3. Intuition

Imagine you are looking at a barcode where lines represent characters, and the thickness of the line represents how many times that character repeats.

• "hello" becomes [h:1, e:1, l:2, o:1]
• "heeellooo" becomes [h:1, e:3, l:2, o:3]

The Strategy: Run-Length Encoding (RLE) Instead of comparing raw strings character by character, we first compress them into their “DNA sequences” of characters and counts. Once compressed, comparing two strings becomes a matter of applying a few simple rules per group:

1. Characters must match: char1 == char2.
2. Count constraints:
   • You cannot shrink a group: count1 >= count2.
   • If lengths differ, the target group must be extended to at least 3 characters: If count1 != count2, then count1 >= 3.

---

4. Solutions

Java

Go

class Solution {
  public int expressiveWords(String s, String[] words) {
    RLE srle = new RLE(s);
    int ans = 0;

    for(String w : words) {
      RLE wrle = new RLE(w);
      if(isStretchy(srle, wrle)) {
        ans++;
      }
    }

    return ans;
  }

  public boolean isStretchy(RLE srle, RLE wrle) {
    if (srle.chars.size() != wrle.chars.size()) return false;

    for (int i = 0 ; i < srle.chars.size() ; i++) {
      char ch1 = srle.chars.get(i);
      char ch2 = wrle.chars.get(i);

      if (ch1 != ch2) return false;

      int c1 = srle.counts.get(i);
      int c2 = wrle.counts.get(i);

      if (c1 < c2) return false;                   // Cannot shrink
      if (c1 != c2 && c1 < 3) return false;        // Standard limit >= 3 rule
    }

    return true;
  }

  class RLE {
    List<Character> chars;
    List<Integer> counts;

    public RLE(String str) {
      int i = 0;
      List<Character> newChars = new ArrayList<>();
      List<Integer> newCounts = new ArrayList<>();

      while(i < str.length()) {
        char c = str.charAt(i);
        int j = i;
        newChars.add(c);

        while(j < str.length() && str.charAt(j) == c) {
          j++;
        }
        newCounts.add(j - i); // Calculate group length
        i = j;
      }
      this.chars = newChars;
      this.counts = newCounts;
    }
  }
}

package main

type RLE struct {
	chars  []byte
	counts []int
}

func getRLE(s string) RLE {
	var chars []byte
	var counts []int
	n := len(s)

	for i := 0; i < n; {
		c := s[i]
		j := i
		for j < n && s[j] == c {
			j++
		}
		chars = append(chars, c)
		counts = append(counts, j-i)
		i = j
	}
	return RLE{chars, counts}
}

func isStretchy(sRLE, wRLE RLE) bool {
	if len(sRLE.chars) != len(wRLE.chars) {
		return false
	}

	for i := 0; i < len(sRLE.chars); i++ {
		if sRLE.chars[i] != wRLE.chars[i] {
			return false
		}

		c1 := sRLE.counts[i]
		c2 := wRLE.counts[i]

		if c1 < c2 {
			return false
		}
		if c1 != c2 && c1 < 3 {
			return false
		}
	}
	return true
}

func expressiveWords(s string, words []string) int {
	sRLE := getRLE(s)
	ans := 0

	for _, w := range words {
		if isStretchy(sRLE, getRLE(w)) {
			ans++
		}
	}

	return ans
}

---

5. Complexity Analysis

Strategy	Time	Space	Notes
Run-Length Encoding	O(S + W)	O(S + W)	Linear scan. Space depends on unique character groups.

S is the length of s, W is the total length of all words in words.