## Find Company Tickers Mentioned in a News Headline ### Problem Implement `findMentionedTickers(companyNames, tickers, headline)`. `companyNames[i]` maps to `tickers[i]`. Tokenize strings into words, match company names as consecutive whole words in the headline, and return the tickers of all matched companies in mapping input order. Return each ticker at most once, even if its company is mentioned repeatedly. Matching is case-insensitive for ASCII letters. A word is a maximal nonempty run of ASCII letters or digits. Every other headline character is a separator. Each company name is already canonical: one or more words separated by a single ASCII space, with no leading or trailing space. If one name is a prefix of another, both count when both full word sequences occur. For example, the headline words `Bank of America` match both `Bank` and `Bank of America` if both names are present in the mapping. ### Function Contract - Python: `def findMentionedTickers(companyNames: list[str], tickers: list[str], headline: str) -> list[str]` - JavaScript: `function findMentionedTickers(companyNames, tickers, headline)` accepts two string arrays and one string and returns a string array. - Java: `List<String> findMentionedTickers(List<String> companyNames, List<String> tickers, String headline)` - C++: `vector<string> findMentionedTickers(const vector<string>& companyNames, const vector<string>& tickers, const string& headline)` Do not mutate either input array. ### Examples ```text companyNames = ["Alpha Labs", "Beta Systems", "International Widgets"] tickers = ["ALAB", "BSYS", "IWGT"] headline = "Beta Systems partners with International Widgets; Alpha Labs responds." output = ["ALAB", "BSYS", "IWGT"] ``` The output follows mapping order, not headline order. ```text companyNames = ["Bank", "Bank of Northland", "Acme 2"] tickers = ["BANK", "BNK", "ACM2"] headline = "BANK OF NORTHLAND expands; Acme-2 launches." output = ["BANK", "BNK", "ACM2"] ``` The hyphen separates `Acme` and `2` into two consecutive words, so the canonical two-word name `Acme 2` matches. ```text companyNames = ["North Star", "South Star"] tickers = ["NSTAR", "SSTAR"] headline = "Market update with no named company" output = [] ``` ### Constraints - `1 <= companyNames.length == tickers.length <= 3,000`. - A company name contains at most `12` words and at most `128` ASCII characters. - Company names are unique after ASCII case-folding; tickers are unique. - A ticker matches `[A-Z][A-Z0-9.]{0,9}`. - The headline contains only printable ASCII characters from U+0020 through U+007E. - Let `B` be the byte length of `[companyNames,tickers,headline]` serialized as compact UTF-8 JSON. There is no whitespace outside strings; quotation marks and reverse solidus characters use their shortest required JSON escapes; all other permitted characters are encoded directly. Inputs satisfy `B <= 96,000`. - Let `R` be the compact UTF-8 JSON byte length of the returned ticker array under the same rule. Inputs guarantee `R <= 96,000`, so serialized input plus result is at most `192,000` bytes. - If `H` is the number of headline words and `M` the number of matched names, target `O(B + 12H + M + R)` time and `O(B)` auxiliary space. ```hint Reuse shared name prefixes Index company-name word sequences together so the same headline position is not compared independently with every full company name. ``` ### Discussion Requirements 1. Explain how tokenization prevents matching `Meta` inside `Metadata`. 2. Show how one traversal can recognize both a shorter name and a longer name that extends it. 3. Explain how matched names are converted to unique tickers in mapping order. 4. State why scanning every company name against the entire headline misses the target complexity.