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.
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.
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.