# "(())()" -> good;
# "(()" -> bad
function goodparens(s::String)::Bool
    nesting = 0
    for c in s
        if c == '('
            nesting += 1
        elseif c == ')'
            nesting -= 1
        end
        if nesting < 0
            return false
        end
    end
    if nesting != 0
        false
    else
        true
    end
end

# "[()]{}" -> good; "[(])" -> bad
function goodmultiparens(s::String)::Bool
    stack::Vector{Char} = []
    for c in s
        if c in ['(', '[', '{']
            push!(stack, c)
        elseif c in [')', ']', '}']
            o = pop!(stack);
            if (c == ')' && o == '(') || (c==']' && o == '[') || (c=='}' && o == '{')
                continue
            else
                return false
            end
        end
    end
    length(stack) == 0
end

function ad_extract_prefixes(strings::AbstractVector{String}, l=1)
    prefixes = Tuple{Int, String}[]
    for (i, s) = enumerate(strings)
        if length(s) < l || (!isempty(prefixes) && (@view s[begin:l]) == prefixes[end][2])
            continue
        end
        push!(prefixes, (i, s[begin:l]))
    end
    prefixes
end

# Without tracking
function ad_longest_path(adj::Matrix{Bool}, start)::Int
    neighbors = findall(@view adj[start,:])
    if isempty(neighbors)
        1
    else
        1 + maximum(ad_longest_path(adj, n) for n = neighbors)
    end
end

function ad_longest_path_tracking(adj::Matrix{Bool}, start, L=0, Lmax=[0], byL=zeros(Int, size(adj, 1)))
    neighbors = findall(@view adj[start,:])
    if isempty(neighbors)
        if L+1 > Lmax[1]
            byL[L+1] = start
            Lmax[1] = L+1
        end
        L+1
    else
        longest = 0
        for n = neighbors
            L_ = ad_longest_path_tracking(adj, n, L+1, Lmax, byL)
            longest = max(longest, L_)
            if L_ == Lmax[1]
                byL[L+1] = start
            end
        end
        longest
    end
end

"""
https://interviewing.io/questions/alien-dictionary
"""
function alien_dictionary(strings::AbstractVector{String})::String
    adj = zeros(Bool, 26, 26)
    char_to_num(c) = 1 + c - 'a'
    num_to_char(n) = 'a' - 1 + n

    max_str_len = maximum(length.(strings))

    for prefix_len = 0:max_str_len
        prefixes = ad_extract_prefixes(strings, prefix_len)

        for (start, pref) = prefixes
            # Loop through strings for each prefix
            
            for entry = start+1:length(strings)
                prev, next = strings[entry-1], strings[entry]
                if !startswith(next, pref)
                    break
                end
                if length(prev) == prefix_len || length(next) == prefix_len
                    continue
                end
                prev_c, next_c = prev[prefix_len+1], next[prefix_len+1]
                if prev_c == next_c
                    continue
                end
                adj[char_to_num(prev_c), char_to_num(next_c)] = true
            end
        end
    end
    start = char_to_num(strings[begin][begin])
    byL = zeros(Int, 26)
    L = ad_longest_path_tracking(adj, start, 0, [0], byL)
    String(num_to_char.(byL[1:L]))
end