Input: encoded_string = "John000Doe000123"
Output: {'first_name': 'John', 'last_name': 'Doe', 'id': '123'}

Input: encoded_string = "Alice0Bob099"
Output: {'first_name': 'Alice', 'last_name': 'Bob', 'id': '99'}

Input: encoded_string = "000000777"
Output: {'first_name': '', 'last_name': '', 'id': '777'} (If split results in empty strings for first/last name)

import re
from typing import Dict

class Solution:
    def parse_encoded_string(self, encoded_string: str) -> Dict[str, str]:
        # Your code here
        pass

Solution: Parsing Encoded String

Approach 1: Using Regular Expressions (re.split()) - Optimal & Concise

The most Pythonic and often most robust way to handle splitting by a variable-length delimiter (like "one or more zeros") is using regular expressions, specifically the re.split() function.

The regex pattern r'0+' means "match one or more occurrences of the character '0'". re.split(r'0+', encoded_string) will split the string wherever it finds one or more zeros, and it will return a list of the non-delimiter parts.

import re
from typing import Dict

class Solution:
    def parse_encoded_string_regex(self, encoded_string: str) -> Dict[str, str]:
        # The pattern '0+' matches one or more occurrences of '0'.
        # re.split will split the string by these sequences of zeros.
        parts = re.split(r'0+', encoded_string)
        
        # re.split might produce empty strings if the string starts or ends with
        # the delimiter, or if delimiters are effectively next to non-delimiter parts
        # that are empty. For example, "00A0B00C" -> ['', 'A', 'B', 'C', ''].
        # However, the problem implies a structure part1part2part3.
        # If the string starts with zeros, the first part will be empty.
        # e.g., "000Doe000123" -> ['', 'Doe', '123']
        # We need to ensure we always have 3 parts for assignment, even if some are empty.

        # A simple way to handle cases where fewer than 3 parts are extracted
        # (e.g., if string is just "123" with no zeros, re.split returns ['123'])
        # or if it starts/ends with zeros leading to empty strings in parts.
        # We expect 3 logical segments.

        # If string starts with zeros: parts[0] will be ''.
        # If first name is missing and then zeros: e.g., "000Doe000123" parts will be ['', 'Doe', '123']
        # If first and last are missing: e.g., "000000123" parts will be ['', '', '123']

        # Filter out empty strings that might arise from leading/trailing/consecutive delimiters
        # if the actual content parts are what we want. 
        # However, the problem specifies the ID contains no zeros, implying a structure.
        # "John000Doe000123" -> ['John', 'Doe', '123']
        # "00John00Doe0123" -> ['', 'John', 'Doe', '123'] - this doesn't fit the 3-part model directly.
        # The problem implies a strict structure of `first0+last0+id`.
        # If `re.split` yields `['', '', '123']` for "000000777", it's fine.

        # Assuming the structure will always yield 3 significant segments based on the problem.
        # If the string can be like "000IDONLY" which splits to ['', 'IDONLY'], we need adjustment.
        # But problem says "first name, last name, and an ID" implies 3 parts.
        
        if len(parts) == 3:
            first_name, last_name, id_str = parts[0], parts[1], parts[2]
        elif len(parts) == 2 and encoded_string.startswith('0'): # Case "0+LastName0+ID"
            first_name = ""
            last_name, id_str = parts[1], parts[0] # if split('') -> ['', 'LastName', 'ID']
                                        # if split('0LastName0ID') -> ['LastName', 'ID']
                                        # Correcting for "000Doe000123" -> parts == ['', 'Doe', '123']
            # The split behavior: "0A0B" -> ['', 'A', 'B']
            # "A00B0C" -> ['A', 'B', 'C']
            # "00A00B0C" -> ['', 'A', 'B', 'C']
            # "A00B00" -> ['A', 'B', '']
            # We need exactly 3 non-empty segments between the zero delimiters.
            # The problem structure implies `name0+name0+id`. re.split is robust.
            # If string is `000000777`, re.split(r'0+', "000000777") -> ['', '777', ''] if trailing zeros are treated
            # Actually, re.split(r'0+', "000000777") -> ['', '777'] if it ends with non-zero.
            # And re.split(r'0+', "John000Doe000123") -> ['John', 'Doe', '123']
            # And re.split(r'0+', "00John00Doe00123") -> ['', 'John', 'Doe', '123'] -- this is 4 parts.
            # The prompt implies only 3 parts. A better regex or parsing logic might be needed for full robustness.
            # Given "The ID itself contains no zeros" and "separators are one or more zeros"
            # and "always three parts", a simple re.split should yield 3 elements.
            # If parts = ['', '', '777'] for "000000777", then:
            if len(parts) >= 3: # Handles ['', 'John', 'Doe', '123'] from "0John0Doe0123"
                 # This will pick the first 3 non-empty parts or fill from left.
                 # A more robust split would be on a pattern that *captures* the non-zero parts.
                 # However, re.split(r'0+', s) is what's suggested.
                 # If s = "000000777", parts = ['', '777']. This doesn't directly map to 3.
                 # Let's assume the problem implies a structure that results in 3 segments from split.
                 # For "John000Doe000123" -> parts = ['John', 'Doe', '123'] (len 3)
                 # For "000Doe000123" -> parts = ['', 'Doe', '123'] (len 3)
                 # For "000000123" -> parts = ['', '', '123'] (len 3) - this interpretation is tricky for re.split
                 # re.split(r'0+', '000000123') -> ['', '123']. This is where the approach needs refinement.
                 # Let's use re.findall to capture non-zero sequences.
                 
                non_zero_parts = re.findall(r'[^0]+', encoded_string)
                if len(non_zero_parts) == 3:
                    first_name, last_name, id_str = non_zero_parts
                elif len(non_zero_parts) == 2: # "LastName0+ID" or "FirstName0+ID" (assuming ID is always last)
                                        # The problem statement "first name, last name, and an ID" suggests all three will be parseable.
                                        # "000Doe000123" findall -> ['Doe', '123'] -- this still needs context.
                                        # The split method is simpler if it reliably gives 3 parts.
                                        # Let's stick to re.split and handle its output based on expected structure.
                # Given the problem "These parts are separated by one or more zeros."
                # String "000ID" -> split -> ['', 'ID']
                # String "Name000ID" -> split -> ['Name', 'ID']
                # String "First00Last00ID" -> split -> ['First', 'Last', 'ID']
                # We are guaranteed three parts separated by zeros. This means two zero separators.
                # So, `re.split` should always give 3 elements.
            else: # Fallback if re.split doesn't give 3 parts, which shouldn't happen given constraints
                  # or handle error. For this problem, assume parts will be 3.
                  return {"first_name": "", "last_name": "", "id": ""} # Or raise error

        return {
            "first_name": parts[0],
            "last_name": parts[1],
            "id": parts[2]
        }

Note on re.split(): If the string starts or ends with the delimiter, re.split() can produce empty strings at the beginning or end of the resulting list. E.g., re.split('0+', '0A0B0') yields ['', 'A', 'B', '']. The problem statement "separated by one or more zeros" and "ID itself contains no zeros" implies a structure like 0+0+. If leading parts are empty (e.g., "000Doe000123"), re.split(r'0+', "000Doe000123") would give ['', 'Doe', '123']. This solution assumes re.split() will yield exactly 3 elements corresponding to first, last, and ID. If the string was just "007", re.split(r'0+', "007") gives ['', '7'] which wouldn't fit the 3-part model easily. The problem statement implies the presence of the separators if all three parts are meant to be distinct. The example "000000777" suggests the first two parts can be empty. A simpler re.split() on `0+` for "000000777" yields `['', '777']`. The most robust way for exactly 3 parts separated by `0+` would be using `re.match` with capturing groups for a pattern like `^([^0]*)0+([^0]*)0+([^0]+)$`, but `re.split` is suggested in the problem-solving hint. If we assume the problem guarantees a structure where `re.split(r'0+', s)` results in 3 segments (even if some are empty initially), then the code is simpler. Given the "ID itself contains no zeros" and "separated by one or more zeros", `re.split(r'0+')` on `John000Doe000123` is `['John', 'Doe', '123']`. For `000000777`, `re.split(r'0+', '000000777')` is `['', '777']`. To make this robust for the example `000000777` -> `{'first_name': '', 'last_name': '', 'id': '777'}`, we should use `re.match` with groups, or parse more carefully.

Revised Regex Approach with Capturing Groups (More Robust for this specific 3-part structure):

import re
from typing import Dict

class Solution:
    def parse_encoded_string_regex_capture(self, encoded_string: str) -> Dict[str, str]:
        # Pattern to capture three groups separated by one or more zeros.
        # Group 1 (first_name): zero or more non-zero characters. ([^0]*)
        # Separator 1: one or more zeros. (0+)
        # Group 2 (last_name): zero or more non-zero characters. ([^0]*)
        # Separator 2: one or more zeros. (0+)
        # Group 3 (id): one or more non-zero characters. ([^0]+) - ID cannot be empty if present
        # ^ and $ ensure the whole string matches this structure.
        pattern = r"^([^0]*)0+([^0]*)0+([^0]+)$"
        
        match = re.match(pattern, encoded_string)
        
        if match:
            first_name = match.group(1)
            last_name = match.group(2)
            id_str = match.group(3)
            return {
                "first_name": first_name,
                "last_name": last_name,
                "id": id_str
            }
        else:
            # Handle cases that don't fit the exact 3-part structure separated by zeros
            # For example, if it's just an ID, or only two parts.
            # The problem implies this structure, but for robustness:
            # Check if it's just an ID (no zeros)
            if '0' not in encoded_string and encoded_string:
                return {"first_name": "", "last_name": "", "id": encoded_string}
            # A simpler split approach as initially suggested for an interview might assume re.split works perfectly.
            # For "000000777" with re.split(r'0+', "000000777") giving ['', '777']
            # The prompt example "000000777" output implies first_name='', last_name=''.
            # This requires careful handling of the `re.split` output length or the capture group regex.
            # The capturing group approach handles "000000777" correctly IF the pattern is adjusted:
            # For "000000777", a pattern like r"^0*([^0]*)0*([^0]*)0*([^0]+)$" might be needed, 
            # or r"^([^0]*)0+([^0]*)0+([^0]+)$|^(0*)([^0]+)$" to handle only ID.
            # Given the hint's suggestion of `re.split`, let's refine the split-based one.
            
            # Refined re.split based on problem's examples:
            parts = re.split(r'0+', encoded_string)
            # "John000Doe000123" -> ['John', 'Doe', '123']
            # "Alice0Bob099" -> ['Alice', 'Bob', '99']
            # "000000777" -> ['', '777'] -- This case makes simple indexing parts[0], parts[1], parts[2] fail.
            
            # Let's assume the problem implies the structure will give 3 elements from split
            # if it can be parsed into first, last, id. Or be more specific about the parts.
            # The most robust way to get exactly 3 parts is usually with re.match and groups.
            # If we must use re.split, and the example for "000000777" is key:
            if len(parts) == 3: # "first0+last0+id" or "0+last0+id" or "first0+0+id"
                 return {"first_name": parts[0], "last_name": parts[1], "id": parts[2]}
            elif len(parts) == 2: # "0+0+id" or "name0+id" or "0+name+id"
                # If original string started with '0', parts[0] is empty.
                if encoded_string.startswith('0'): # implies first_name is empty or first_name and last_name are empty
                                        # "00last00id" -> ['', 'last', 'id'] -- this would be len 3
                                        # "0000id" -> ['', 'id']
                    return {"first_name": "", "last_name": parts[0] if parts[0] != encoded_string[-len(parts[1]):] else "", "id": parts[1]}
                else: # "first0+id"
                    return {"first_name": parts[0], "last_name": "", "id": parts[1]}
            elif len(parts) == 1 and parts[0] == encoded_string: # Only ID, no zeros
                 return {"first_name": "", "last_name": "", "id": parts[0]}
            
            # Fallback for unexpected format or if clarification is needed on "000000777"
            raise ValueError("Encoded string format not as expected or ambiguous for re.split.")

# The re.match approach with capturing groups is generally more robust for fixed structures.
# The problem wording "separated by one or more zeros" + "ID contains no zeros" + "first, last, id"
# strongly suggests a fixed structure that `re.split(r'0+', s)` should yield 3 parts.
# `re.split('0+', 'John00Doe0123')` -> `['John', 'Doe', '123']`
# `re.split('0+', '0John0Doe0123')` -> `['', 'John', 'Doe', '123']` - this would fail simple indexing.
# `re.split('0+', '0000ID')` -> `['', 'ID']`
# The most straightforward interpretation for `re.split` given the problem's aim is that the "useful" parts are what remain.
# A simple `filter(None, parts)` or `[p for p in parts if p]` can get non-empty parts.
# If we must return 3 keys, even if some are empty:
class SolutionFinal:
    def parse_encoded_string(self, encoded_string: str) -> Dict[str, str]:
        # This pattern captures the non-zero parts.
        # ([^0]*) - first name (can be empty)
        # 0+ - one or more zeros as separator
        # ([^0]*) - last name (can be empty)
        # 0+ - one or more zeros as separator
        # ([^0]+) - ID (must have at least one char, and no zeros as per problem)
        pattern = r"^([^0]*)0+([^0]*)0+([^0]+)$" 
        match_obj = re.fullmatch(pattern, encoded_string)

        if match_obj:
            return {
                "first_name": match_obj.group(1),
                "last_name": match_obj.group(2),
                "id": match_obj.group(3)
            }
        else:
            # Handle cases that don't fit the primary 3-part pattern
            # E.g., "000ID", "FirstName000ID"
            # Try to find the last non-zero part as ID, and work backwards for names if possible.
            parts = re.split(r'0+', encoded_string)
            # Filter out empty strings that re.split might produce from leading/trailing zeros.
            filtered_parts = [p for p in parts if p] 

            if not filtered_parts: # e.g. "000"
                return {"first_name": "", "last_name": "", "id": ""}
            
            id_str = filtered_parts[-1]
            last_name = filtered_parts[-2] if len(filtered_parts) > 1 else ""
            first_name = filtered_parts[-3] if len(filtered_parts) > 2 else ""
            
            # This logic needs to be very careful if the example "000000777" should yield
            # first_name="", last_name="", id="777".
            # If parts from re.split("0+", "000000777") is ['', '777'], then filtered_parts is ['777'].
            # Then id_str = '777', last_name = '', first_name = ''. This works for example 3.

            if len(filtered_parts) == 1: # Only ID part was found (e.g., "123" or "000123")
                 return {"first_name": "", "last_name": "", "id": filtered_parts[0]}
            elif len(filtered_parts) == 2: # Last name and ID, or First name and ID
                 # Heuristic: assume it's last_name, id if it seems like "LastName0+ID"
                 # This is where ambiguity lies without a stricter pattern or more info.
                 # For "John000123", filtered_parts is ['John', '123'] -> fn='John', ln='', id='123'
                 return {"first_name": filtered_parts[0], "last_name": "", "id": filtered_parts[1]}
            elif len(filtered_parts) >= 3: # Should be caught by re.fullmatch ideally
                 return {"first_name": filtered_parts[0], "last_name": filtered_parts[1], "id": filtered_parts[2]}
            else:
                raise ValueError("Invalid encoded string format.")


# Simpler `re.split` based solution, assuming it reliably gives 3 segments or handles empty leading parts.
class SolutionSplit:
    def parse_encoded_string(self, encoded_string: str) -> Dict[str, str]:
        parts = re.split(r'0+', encoded_string)
        # "John000Doe000123" -> ['John', 'Doe', '123']
        # "000Doe000123" -> ['', 'Doe', '123']
        # "000000777" -> ['', '777']
        # "John000000777" -> ['John', '', '777']

        if len(parts) == 3:
            return {"first_name": parts[0], "last_name": parts[1], "id": parts[2]}
        elif len(parts) == 2: # This means first_name was empty and string started with zeros
            return {"first_name": parts[0], "last_name": "", "id": parts[1]} # Corrected for "000000777" example if parts=['','777']
                                                                         # and for "John000777" if parts=['John','777']
                                                                         # This depends on how example "000000777" is interpreted. 
                                                                         # If it means "first_name='', last_name='', id='777'", then if len(parts)==2 and parts[0]=='', then it's this case.
            if parts[0] == '': # Handles "0...0LAST0...0ID" and "0...0ID" (if ID is only non-empty)
                return {"first_name": "", "last_name": "", "id": parts[1]}
            else: # Handles "FIRST0...0ID"
                return {"first_name": parts[0], "last_name": "", "id": parts[1]}
        elif len(parts) == 1 and parts[0] != '': # Only ID, no zeros involved (e.g. "123")
            return {"first_name": "", "last_name": "", "id": parts[0]}
        else: # e.g. "" or "000"
             return {"first_name": "", "last_name": "", "id": ""} # Or raise error

The SolutionSplit version is simpler but makes assumptions about how re.split handles edge cases of missing parts. For an interview, the SolutionFinal using re.fullmatch with capturing groups is more robust for the defined 3-part structure, or the SolutionSplit can be presented with a clear discussion of how it handles the "000000777" example to produce the desired empty strings for first/last names.

Approach 2: Iterative Parsing (Manual "Brute Force")

This approach involves manually iterating through the string, identifying parts based on encountering '0's.

from typing import Dict

class Solution:
    def parse_encoded_string_manual(self, encoded_string: str) -> Dict[str, str]:
        parts = []
        current_part = []
        i = 0
        n = len(encoded_string)

        while i < n:
            if encoded_string[i] != '0':
                current_part.append(encoded_string[i])
                i += 1
            else: # Found a zero
                if current_part or (not parts and i == 0) or (not parts and encoded_string[i-1] == '0' and len(parts) < 2):
                    # Add part if it's non-empty, or if it's an initial empty part before first/second zero sequence
                    parts.append("".join(current_part))
                current_part = []
                # Skip all consecutive zeros
                while i < n and encoded_string[i] == '0':
                    i += 1
        
        # Add the last part (which is the ID and contains no zeros)
        if current_part or not parts or encoded_string.endswith('0') and len(parts) < 3:
             parts.append("".join(current_part))

        # Assign to dictionary, handling cases where parts might be missing (e.g. "000ID")
        result = {"first_name": "", "last_name": "", "id": ""}
        if len(parts) == 3:
            result["first_name"] = parts[0]
            result["last_name"] = parts[1]
            result["id"] = parts[2]
        elif len(parts) == 2: # Assume "00last00id" or "first00id"
            if parts[0] == "": # Likely "00last00id" or "0000id"
                result["id"] = parts[1] # This would be "id" for "0000id"
            else: # "first00id"
                result["first_name"] = parts[0]
                result["id"] = parts[1]
        elif len(parts) == 1 and parts[0]: # Only ID
            result["id"] = parts[0]
        
        # Refinement for the "000000777" example to get {"first_name": "", "last_name": "", "id": "777"}
        # The above logic for manual parsing is getting complex. 
        # A simpler iterative approach would be to find the indices of zero sequences.
        return result

The manual iterative parsing can become quite complex to correctly handle all edge cases of where the zeros might appear relative to empty parts, especially matching the "000000777" example. The regex approach with capturing groups (like in `SolutionFinal`) is generally more robust and declarative for such structured parsing.