Count substrings and generate TOC

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 0s and 1s.
• All 0s in the substring are contiguous, and all 1s 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.

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

Example 1

Input: "00110011"
Output: 6

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

Example 2

Input: "10101"
Output: 4

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

Hints

1. Think about the lengths of consecutive runs of the same character instead of checking every substring.
2. 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

Example 1

Input: ["# Introduction", "Some text", "## Goal", "## Scope", "# Conclusion", "## Thanks"]
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.

Example 2

Input: ["## Orphan section", "# Chapter One", "## First", "Body", "# Chapter Two"]
Output: ["1. Chapter One", "1.1. First", "2. Chapter Two"]

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

Hints

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