PracHub
QuestionsCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates string-processing and tree-construction skills, including efficient removal of adjacent or k-sized duplicate groups in strings and building a binary tree from a level-order array to compute properties such as the sum of left leaves.

  • medium
  • Grammarly
  • Coding & Algorithms
  • Software Engineer

Remove adjacent duplicates and handle tree input

Company: Grammarly

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are asked three related coding questions. ## 1) Remove adjacent duplicates (repeatedly) Given a string `s` (lowercase English letters), repeatedly remove any pair of **adjacent equal characters** until no such pair exists. - **Input:** `s` - **Output:** the final string after all removals **Example:** - `s = "abbaca"` → remove `bb` → `aaca` → remove `aa` → `ca` **Constraints (typical):** `1 <= |s| <= 1e5`. ## 2) Follow-up: remove groups of size k Given a string `s` and an integer `k`, repeatedly remove any **group of exactly `k` adjacent equal characters** until no more removals are possible. - **Input:** `s`, `k` - **Output:** final string **Example:** - `s = "deeedbbcccbdaa", k = 3` → output `"aa"` **Constraints (typical):** `1 <= |s| <= 1e5`, `2 <= k <= 1e4`. ## 3) Tree problem, but input is an array (must build the tree) You are given a binary tree in **level-order array form** (not `TreeNode` objects). `null` indicates a missing child. Build the binary tree and compute: > The **sum of all left leaf nodes** (a left leaf is a leaf node that is the left child of its parent). - **Input:** array `arr` of integers and `null`s, in level-order - **Output:** integer sum **Example:** - `arr = [3,9,20,null,null,15,7]` → left leaves are `9` and `15` → output `24` **Notes:** You must construct the tree from the array representation before computing the answer.

Quick Answer: This question evaluates string-processing and tree-construction skills, including efficient removal of adjacent or k-sized duplicate groups in strings and building a binary tree from a level-order array to compute properties such as the sum of left leaves.

Remove Adjacent Duplicates (Repeatedly)

Given a string `s` of lowercase English letters, repeatedly remove any pair of **adjacent equal characters** until no such pair exists. Return the final string. This is a classic stack problem: scan left to right and use a stack to cancel a character against the top of the stack whenever they are equal. **Example:** `s = "abbaca"` → remove `bb` → `"aaca"` → remove `aa` → `"ca"`. Output: `"ca"`. **Constraints:** `1 <= |s| <= 1e5`, `s` consists of lowercase English letters.

Constraints

  • 1 <= |s| <= 1e5
  • s consists of lowercase English letters

Examples

Input: ("abbaca",)

Expected Output: "ca"

Explanation: Remove bb to get aaca, then remove aa to get ca.

Input: ("azxxzy",)

Expected Output: "ay"

Explanation: Remove xx -> azzy, remove zz -> ay.

Input: ("a",)

Expected Output: "a"

Explanation: Single character, nothing to remove.

Input: ("aa",)

Expected Output: ""

Explanation: The single adjacent pair is removed, leaving empty string.

Input: ("aaa",)

Expected Output: "a"

Explanation: First two a's cancel, one a remains.

Input: ("abccba",)

Expected Output: ""

Explanation: cc cancels -> abba, bb cancels -> aa, aa cancels -> empty.

Input: ("abc",)

Expected Output: "abc"

Explanation: No adjacent equal characters.

Hints

  1. Use a stack. Push each character; if it equals the current top, pop instead of pushing.
  2. Removals can cascade — after popping, the new top may match the next character. A stack handles this automatically.
  3. The final answer is the stack contents joined from bottom to top.

Remove All Adjacent Duplicates II (Groups of Size k)

Given a string `s` and an integer `k`, repeatedly remove any **group of exactly `k` adjacent equal characters** until no more removals are possible. Return the final string. (It can be proven the result is unique.) Use a stack of `[character, count]` pairs. When the running count of the top character reaches `k`, pop the whole group. **Example:** `s = "deeedbbcccbdaa", k = 3` → output `"aa"`. **Constraints:** `1 <= |s| <= 1e5`, `2 <= k <= 1e4`, `s` consists of lowercase English letters.

Constraints

  • 1 <= |s| <= 1e5
  • 2 <= k <= 1e4
  • s consists of lowercase English letters

Examples

Input: ("deeedbbcccbdaa", 3)

Expected Output: "aa"

Explanation: Remove eee -> dddbbcccbdaa? Process with a stack: eee(k=3) removed, then ddd removed, then ccc removed, then bbb removed, leaving daa? Final is aa.

Input: ("abcd", 2)

Expected Output: "abcd"

Explanation: No group of 2 equal adjacent chars exists.

Input: ("pbbcggttciiippooaais", 2)

Expected Output: "ps"

Explanation: Each double cancels, cascading down to ps.

Input: ("aaa", 3)

Expected Output: ""

Explanation: Exactly 3 a's form a removable group.

Input: ("a", 2)

Expected Output: "a"

Explanation: Only one a, no group of size 2.

Input: ("aaaa", 2)

Expected Output: ""

Explanation: First two a's removed, remaining two a's removed.

Input: ("aabbaa", 2)

Expected Output: ""

Explanation: aa removed, bb removed, then the remaining aa removed.

Hints

  1. Track counts on the stack: store pairs of (character, consecutive count) instead of single characters.
  2. When the top's count reaches k, pop the entire entry — the characters before it may now merge with what follows.
  3. Rebuild the answer by repeating each remaining character by its stored count.

Sum of Left Leaves (Build Tree From Level-Order Array)

You are given a binary tree in **level-order array form** (not `TreeNode` objects). `null` indicates a missing child. First **build the binary tree** from this array, then compute the **sum of all left leaf nodes**. A *left leaf* is a leaf node (no children) that is the **left child** of its parent. **Example:** `arr = [3, 9, 20, null, null, 15, 7]` → the left leaves are `9` (left child of `3`) and `15` (left child of `20`) → output `24`. The array is in standard LeetCode-style level-order: children of a node are only emitted when the node itself is non-null, and trailing positions for null nodes are skipped. **Notes:** You must construct the tree from the array representation before computing the answer. Values may be negative; an empty array returns `0`. In the Python harness, `null` is passed as Python `None`.

Constraints

  • 0 <= number of nodes <= 1e4
  • Node values fit in a signed 32-bit integer (may be negative)
  • Array is in LeetCode-style level-order with null for missing children

Examples

Input: ([3,9,20,None,None,15,7],)

Expected Output: 24

Explanation: Left leaves are 9 (left child of 3) and 15 (left child of 20); 9 + 15 = 24.

Input: ([1],)

Expected Output: 0

Explanation: Root only, no left leaves.

Input: ([1,2,3,4,5,None,None],)

Expected Output: 4

Explanation: Node 4 is the left child of 2 and is a leaf; node 3 is a leaf but a right child. Sum = 4.

Input: ([],)

Expected Output: 0

Explanation: Empty array, the tree has no nodes.

Input: ([1,None,2,None,3],)

Expected Output: 0

Explanation: Right-skewed tree; every leaf is a right child, so the left-leaf sum is 0.

Input: ([5,3,8,1,4,7,9],)

Expected Output: 8

Explanation: Left leaves are 1 (left child of 3) and 7 (left child of 8); 1 + 7 = 8.

Input: ([-6,-3,5,None,None,-2,8],)

Expected Output: -5

Explanation: Left leaves are -3 (left child of -6) and -2 (left child of 5); -3 + -2 = -5.

Hints

  1. First reconstruct the tree. Use a queue: pop a parent, then consume the next two array slots as its left and right children (a null slot means no child).
  2. Only the non-null nodes are enqueued, matching the LeetCode level-order convention.
  3. Then DFS/BFS: when visiting a node, if its LEFT child is a leaf, add that child's value to the total. Don't add right leaves.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Implement a Transactional Key-Value Store - Grammarly (medium)
  • Merge overlapping corrections - Grammarly
  • Implement string reduction and time map - Grammarly (easy)
  • Solve interval merge and string dedup problems - Grammarly (hard)