How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at J.P. Morgan.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at J.P. Morgan during technical interviews.

Count substrings and generate TOC | J.P. Morgan Coding Question

Quick Overview

This question evaluates string processing, pattern recognition, and parsing competencies—covering counting and grouping in binary substrings and structured line parsing and numbering for a table of contents—within the Coding & Algorithms domain.

Count substrings and generate TOC

Company: J.P. Morgan

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

Solve the following two coding problems. 1. **Count valid binary substrings** Given a string `s` consisting only of `'0'` and `'1'`, count how many substrings satisfy both conditions: - The substring contains the same number of `0`s and `1`s. - All `0`s in the substring are contiguous, and all `1`s in the substring are contiguous. In other words, a valid substring must consist of exactly two consecutive groups, such as `"0011"`, `"1100"`, `"01"`, or `"10"`. Return the total number of valid substrings. 2. **Generate a table of contents** You are given an array of strings `lines`, where each element represents one line in a document. Build a table of contents using the following rules: - A line starting with `"##"` is a **section** and belongs to the most recent chapter. - Otherwise, a line starting with `"#"` is a **chapter**. - All other lines should be ignored. Number chapters and sections in the order they appear: - A chapter should be output as `"<chapter_number>. <title>"` - A section should be output as `"<chapter_number>.<section_number>. <title>"` When a new chapter appears, its section numbering starts again from 1. Return the generated table of contents as an array of strings.

Quick Answer: This question evaluates string processing, pattern recognition, and parsing competencies—covering counting and grouping in binary substrings and structured line parsing and numbering for a table of contents—within the Coding & Algorithms domain.

Part 1: Count Valid Binary Substrings

Given a binary string s containing only '0' and '1', count the number of non-empty substrings where the number of 0s equals the number of 1s and all identical characters in the substring are grouped together. In other words, every valid substring must contain exactly two consecutive blocks, such as '0011', '1100', '01', or '10'. Return the total number of valid substrings.

Constraints

0 <= len(s) <= 100000
s contains only the characters '0' and '1'

Examples

Input: "00110011"

Expected Output: 6

Explanation: The runs are 00, 11, 00, 11. The total is min(2,2) + min(2,2) + min(2,2) = 6.

Input: "10101"

Expected Output: 4

Explanation: Each character forms a run of length 1, so every adjacent pair contributes 1.

Input: ""

Expected Output: 0

Explanation: An empty string has no substrings.

Input: "0"

Expected Output: 0

Explanation: A single character cannot form a substring with equal numbers of 0s and 1s.

Input: "000111000"

Expected Output: 6

Explanation: The runs are 000, 111, 000. The total is min(3,3) + min(3,3) = 6.

Hints

Think about the lengths of consecutive runs of the same character instead of checking every substring.
Each pair of adjacent runs contributes as many valid substrings as the smaller of the two run lengths.

Part 2: Generate a Table of Contents

You are given an array of strings lines, where each string is one line from a document. Build a table of contents using these rules: a line starting with "##" is a section and belongs to the most recent chapter; otherwise, a line starting with "#" is a chapter; all other lines are ignored. Chapters are numbered starting from 1. Sections are numbered within their chapter starting from 1 and reset when a new chapter appears. Output chapters as "<chapter_number>. <title>" and sections as "<chapter_number>.<section_number>. <title>". If a section appears before any chapter, ignore it. The title is the text after removing the heading markers and trimming surrounding spaces.

Constraints

0 <= len(lines) <= 10000
The total length of all strings in lines is at most 100000
Heading lines, if present, start with either '#' or '##'

Examples

Input: ["# Introduction", "Some text", "## Goal", "## Scope", "# Conclusion", "## Thanks"]

Expected Output: ["1. Introduction", "1.1. Goal", "1.2. Scope", "2. Conclusion", "2.1. Thanks"]

Explanation: Only chapter and section lines are included, and section numbering resets after a new chapter.

Input: ["## Orphan section", "# Chapter One", "## First", "Body", "# Chapter Two"]

Expected Output: ["1. Chapter One", "1.1. First", "2. Chapter Two"]

Explanation: The first section is ignored because there is no previous chapter.

Input: []

Expected Output: []

Explanation: An empty document produces an empty table of contents.

Input: ["Plain text", "## Lost", "More text"]

Expected Output: []

Explanation: There are no chapters, so the section is ignored and non-heading lines are skipped.

Input: ["# A", "## B", "## C", "# D", "## E"]

Expected Output: ["1. A", "1.1. B", "1.2. C", "2. D", "2.1. E"]

Explanation: Sections B and C belong to chapter 1, and section numbering restarts for chapter 2.

Hints

Check for lines starting with '##' before checking for '#', otherwise sections may be mistaken for chapters.
Track the current chapter number and the current section count as you scan the lines once from left to right.

Quick Overview