0740MediumArrayStringUnion-FindGraph Theory

Consistent Terminal Voltage Claims

Tracked in this browser only

Trains the technique from

LeetCode 990Satisfiability of Equality Equations

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A test rig has terminals labelled with single lowercase letters. A technician hands you claims, a list of measurements each written as exactly four characters:

claims[i][0] and claims[i][3] are the two terminal labels;
claims[i][1] is '=' when the claim is that the two terminals carry the same voltage, or '!' when the claim is that they carry different voltages;
claims[i][2] is always '='.

So "c==d" claims terminals c and d sit at one voltage, and "c!=d" claims they do not. A claim may name the same terminal on both sides.

Decide whether some assignment of an integer voltage to every terminal label makes all the claims hold at the same time. Return true if such an assignment exists and false otherwise.

Examples

Example 1

Input: claims = ["r==s", "s==t", "t!=r"]
Output: false

The first two claims put `r`, `s` and `t` all at one voltage, which leaves the third claim asking for `t` and `r` to differ while they are forced to agree.

Example 2

Input: claims = ["h==j", "k!=j", "h==m"]
Output: true

Setting `h`, `j` and `m` to 4 and `k` to 9 satisfies every claim: the two sameness claims hold and `k` differs from `j`.

Example 3

Input: claims = ["w!=w"]
Output: false

The claim asks terminal `w` to carry a voltage different from its own, which no assignment can do.

Constraints

1 <= claims.length <= 500
claims[i].length == 4
claims[i][0] is a lowercase English letter.
claims[i][1] is either '=' or '!'.
claims[i][2] is '='.
claims[i][3] is a lowercase English letter.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def claims_consistent(claims: list[str]) -> bool:

Java

public boolean claimsConsistent(String[] claims)

The intended approach

Time O(m) for m claims, up to the near-constant disjoint-set lookup factor.Space O(1) beyond the input: the forest has one slot per letter of the alphabet.

Sameness is transitive, so the equality claims carve the 26 possible labels into groups that must share one voltage. Hold those groups in a disjoint-set forest over 26 slots and merge the two labels of every equality claim, with path halving inside the lookup so the forest stays shallow. Only after all of the merges are in place does a difference claim mean anything: it fails exactly when its two labels have ended up in the same group, which also handles a claim that a terminal differs from itself. If no difference claim fails, distinct integers assigned one per group satisfy everything.

Pythonentry point: claims_consistent

def claims_consistent(claims):
    # merge every "same voltage" claim into a disjoint-set forest first, then
    # test each "different voltage" claim against the resulting groups.
    # O(m) for m claims, with a fixed 26-slot forest.
    root = list(range(26))

    def find(x):
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    for c in claims:
        if c[1] == '=':
            a, b = find(ord(c[0]) - 97), find(ord(c[3]) - 97)
            if a != b:
                root[a] = b
    for c in claims:
        if c[1] == '!':
            if find(ord(c[0]) - 97) == find(ord(c[3]) - 97):
                return False
    return True

The obvious version

Fill a 26 by 26 table of label pairs known to share a voltage from the equality claims, then close the table under transitivity by relaxing through every possible middle label, and finally reject if any difference claim names a pair the table marks as shared.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_claims_consistent(claims):
    """Build a 26x26 table of "provably the same" pairs, close it under
    transitivity by relaxing every middle terminal, then test the inequalities."""
    same = [[False] * 26 for _ in range(26)]
    for i in range(26):
        same[i][i] = True
    for c in claims:
        if c[1] == '=':
            a, b = ord(c[0]) - 97, ord(c[3]) - 97
            same[a][b] = True
            same[b][a] = True
    for mid in range(26):
        for i in range(26):
            if same[i][mid]:
                for j in range(26):
                    if same[mid][j]:
                        same[i][j] = True
    for c in claims:
        if c[1] == '!':
            a, b = ord(c[0]) - 97, ord(c[3]) - 97
            if same[a][b]:
                return False
    return True

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in