Memory Rune Sequencer

Graph Easy 3 views

Like14

The Memory Keepers of the Rune Conservatory protect their vault behind nested rules. Each rule is either a single rune leaf (an uppercase letter) or a requirement {"require": r, "before": X, "after": Y}. This means rune r must appear, with all runes in subtree X strictly before it and all in Y strictly after it. Your mission in Memory Rune Sequencer is to find the Shortest String that satisfies the rule tree.

The "secret sauce" here is Greedy Suffix Merging. Since subtrees might require overlapping characters, you must align the "before" and "after" sequences to reuse as many runes as possible. If multiple strings share the minimum length, return the lexicographically smallest one. You must handle deep nesting and repeat characters with care to ensure the vault remains secure! This challenge is a beautiful exercise in recursive string construction and deterministic alignment, turning a complex set of ancient rules into a precise, efficient key for the vault team.

When the task involves connectivity or route cost, build adjacency carefully and guard against revisiting stale states. Use a visited or best-distance structure to avoid repeated work, and ensure unreachable scenarios return the required fallback value instead of partial traversal results.

Examples

Example 1

Input

rule = "A"

Output

"A"

Explanation

Example with input: rule = "A"

Example 2

Input

rule = {"require": "C", "before": {"require": "B", "before": "A", "after": "A"}, "after": "D"}

Output

"AABC D" (spaces added for clarity: the minimal string is

Explanation

Example with input: rule = {"require": "C", "before": {"require": "B",

Example 3

Input

rule = {"require": "B", "before": "A", "after": "C"}

Output

"ABC"

Explanation

Example with input: rule = {"require": "B", "before": "A", "after": "C

Algorithm Flow

Recommendation Algorithm Flow for Memory Rune Sequencer - Budibadu

Best Answers

java

class Solution {
    public int calculate_lcs_length(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[m][n];
    }
}

javascript

function calculate_lcs_length(s1, s2) {
    const m = s1.length, n = s2.length;
    const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s1[i-1] === s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[m][n];
}

php

function calculate_lcs_length($s1, $s2) {
    $m = strlen($s1); $n = strlen($s2);
    $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            if ($s1[$i-1] == $s2[$j-1]) $dp[$i][$j] = $dp[$i-1][$j-1] + 1;
            else $dp[$i][$j] = max($dp[$i-1][$j], $dp[$i][$j-1]);
        }
    }
    return $dp[$m][$n];
}

python

def calculate_lcs_length(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

rust

pub fn calculate_lcs_length(s1: String, s2: String) -> i32 {
    let m = s1.len(); let n = s2.len();
    let mut dp = vec![vec![0; n + 1]; m + 1];
    let s1_chars: Vec<char> = s1.chars().collect();
    let s2_chars: Vec<char> = s2.chars().collect();
    for i in 1..=m {
        for j in 1..=n {
            if s1_chars[i-1] == s2_chars[j-1] { dp[i][j] = dp[i-1][j-1] + 1; }
            else { dp[i][j] = std::cmp::max(dp[i-1][j], dp[i][j-1]); }
        }
    }
    dp[m][n]
}

typescript

function calculate_lcs_length(s1: string, s2: string): number {
    const m = s1.length, n = s2.length;
    const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s1[i-1] === s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[m][n];
}

Comments (0)

Join the Discussion

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

Memory Rune Sequencer

Examples

Algorithm Flow

Best Answers

Solutions Coming Soon

Related Graph Problems

Catalog Shelf Lineup

Ascending Manifest

Starfall Signal Map

Shortest Path in Weighted Graph

Comments (0)

Join the Discussion