Boggle Game
Updated
Problem statement
You are given an n x n board of lowercase letters and a list of different words.
A word can be placed on the board along a path of cells that spells the word in order. Each step of the path moves to a cell that is directly above, below, left or right of the current cell, and the path never uses a cell twice.
Choose some of the words and place each chosen word along its own path so that no two chosen words share a cell. Each word can be chosen at most once.
Return the largest number of words you can place on the board at the same time.
Function
maxWords(board: char[][], words: String[]) → intExamples
Example 1
board = [["c", "a", "t"], ["o", "r", "e"], ["d", "o", "g"]]words = ["cat", "dog", "core", "ore", "rod"]return = 3Place "cat" on the top row, "ore" on the middle row and "dog" on the bottom row. The three paths use different cells, so 3 words fit. The board has only 9 cells and every word has 3 or more letters, so 4 words cannot fit.
Example 2
board = [["s", "e", "a"], ["t", "o", "p"], ["r", "u", "g"]]words = ["sea", "top", "stop", "rug", "pot"]return = 3A long word is not always a good choice. "stop" fits on the left cell of the top row and then the whole middle row. After that, "rug" still fits on the bottom row, but no word fits on the free cells e and a, so this gives only 2 words.
Instead, place "sea", "top" and "rug" on the three rows. That gives 3 words. "pot" needs the same cells as "top", and every word has at least 3 letters, so 4 words cannot fit in 9 cells.
Example 3
board = [["a", "a"], ["a", "a"]]words = ["aa", "a"]return = 2Place "aa" on the top row and "a" on one cell of the bottom row, for 2 words. A second copy of "aa" would also fit, but each word can be chosen only once.
Example 4
board = [["x"]]words = ["y", "xx"]return = 0"y" does not appear on the board, and "xx" would need the single cell twice. No word fits, so the answer is 0.
Constraints
n == board.length == board[i].length1 <= n <= 4board[i][j]is a lowercase English letter.1 <= words.length <= 121 <= words[i].length <= 8words[i]consists of lowercase English letters.- All the strings in
wordsare different.
More Airbnb Phone Screen questions
- Read Across Sound TracksPHONE SCREEN · Seen Nov 2026
- Text JustificationPHONE SCREEN · Seen Nov 2026
- Decode and Store StringsPHONE SCREEN · Seen Oct 2026
- Print Sentences as TablePHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Detonate Bombs with Chain ReactionsPHONE SCREEN · Seen Aug 2026
- Smallest Common RegionPHONE SCREEN · Seen Aug 2026
- Longest Chain BookingPHONE SCREEN · Seen Aug 2026
- Nested List Iterator with RemovePHONE SCREEN · Seen Jul 2026
- Parse Query StringPHONE SCREEN · Seen May 2026
- Pacific Atlantic Water FlowPHONE SCREEN · Seen May 2023
Similar questions at other companies
- Choose the Next Minesweeper ActionRunloop · PHONE SCREEN
- Word Search IIApple · PHONE SCREENApple interview questions
- Maximum Words in Disjoint Grid PathsIndeed · PHONE SCREENIndeed interview questions
- Word Search IIAmazon · ONSITE INTERVIEW
- Count Eight-Neighbor Unlock PatternsGoogle · ONSITE INTERVIEWGoogle interview questions
- Boggle Word FinderBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Sudoku Puzzle SolverConfluent · PHONE SCREEN · ONSITE INTERVIEWConfluent interview questions
- Visit Desired Attractions Without Reusing a TrailDuolingo · PHONE SCREENDuolingo interview questions
- Word Break IIWex · PHONE SCREEN
- Maximum Currency Conversion Along a Simple PathRippling · PHONE SCREEN · ONSITE INTERVIEWRippling interview questions
Interview reports that mention this question
Airbnb interview experiences
- Airbnb SWE OA: Four-Level Banking System: 1 Experience
- Airbnb Campus and Full-Time SWE OA / Interviews: 9 Experiences
- Airbnb Intern OA and Phone Screens: 17 Experiences (Part 6 of 7)
- Airbnb Intern OA and Onsite Rounds: 16 Experiences (Part 5 of 7)
- Airbnb Intern OA, Diplomacy Game: 19 Experiences (Part 4 of 7)