Luminous Script Segmentation Count

Published at05 Jan 2026

Like15

You are given a script string and a dictionary of allowed phrases. The job is to count how many different ways the full script can be segmented so that every piece is one of those phrases.

This is not about rearranging phrases. The order is fixed by the original script, and every character must be covered exactly once from left to right.

For example, if the script is empty, the answer is 1 because there is exactly one way to segment it: choose nothing. If the script can be broken in multiple valid phrase sequences, all of those count toward the total.

So the task is to count all valid left-to-right segmentations of the script using only the allowed phrases.

Example Input & Output

Example 1

Input

script = "lanternfair", phrases = ["lan","lantern","tern","fair"]

Output

Explanation

The script can be restored as "lantern fair" or "lan tern fair".

Example 2

Input

script = "riverlights", phrases = ["river","light","lights","riverlight"]

Output

Explanation

Only the segmentation "river lights" matches the script.

Example 3

Input

script = "", phrases = ["lantern"]

Output

Explanation

The empty script has one valid segmentation that uses no phrases.

Algorithm Flow

Recommendation Algorithm Flow for Luminous Script Segmentation Count

Solution Approach

This is a counting version of word break, so dynamic programming works well. Let dp[i] mean the number of ways to segment the suffix that starts at position i.

The base case is:

dp[script.length] = 1

That says once we reach the end of the string, we have found one complete valid segmentation.

At each position i, we try every phrase that matches the script starting there. If a phrase of length len fits, then every valid segmentation of the remaining suffix contributes to the current answer:

dp[i] += dp[i + len]

We fill the DP from right to left, or use memoized recursion to compute the same idea on demand.

At the end, dp[0] is the total number of valid segmentations for the whole script.

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public int count_segmentations(String s, String[] dictionary) {
        Set<String> words = new HashSet<>(Arrays.asList(dictionary));
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (words.contains(s.substring(j, i))) {
                    dp[i] += dp[j];
                }
            }
        }
        return dp[n];
    }
}

javascript

function count_segmentations(s, dictionary) {
    const words = new Set(dictionary);
    const n = s.length;
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            if (words.has(s.substring(j, i))) {
                dp[i] += dp[j];
            }
        }
    }
    return dp[n];
}

php

function count_segmentations($s, $dictionary) {
    $words = array_flip($dictionary);
    $n = strlen($s);
    $dp = array_fill(0, $n + 1, 0);
    $dp[0] = 1;
    for ($i = 1; $i <= $n; $i++) {
        for ($j = 0; $j < $i; $j++) {
            if (isset($words[substr($s, $j, $i - $j)])) {
                $dp[$i] += $dp[$j];
            }
        }
    }
    return $dp[$n];
}

python

def count_segmentations(s: str, dictionary: list) -> int:
    words = set(dictionary)
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        for j in range(i):
            if s[j:i] in words:
                dp[i] += dp[j]
    return dp[n]

rust

use std::collections::HashSet;
pub fn count_segmentations(s: String, dictionary: Vec<String>) -> i32 {
    let words: HashSet<String> = dictionary.into_iter().collect();
    let n = s.length(); // Wait, String doesn't have length(), but len()
    let n = s.len();
    let mut dp = vec![0; n + 1];
    dp[0] = 1;
    for i in 1..=n {
        for j in 0..i {
            if words.contains(&s[j..i]) {
                dp[i] += dp[j];
            }
        }
    }
    dp[n]
}

typescript

function count_segmentations(s: string, dictionary: string[]): number {
    const words = new Set(dictionary);
    const n = s.length;
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            if (words.has(s.substring(j, i))) {
                dp[i] += dp[j];
            }
        }
    }
    return dp[n];
}

Related Dynamic Programming Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Luminous Script Segmentation Count

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Dynamic Programming Challenges

Harbor Banner Schedule Slots

Lantern Melody Chain Length

Festival Coin Path Count

River Token Ways

Stair Lantern Routes

Max Vacation Profit

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.