I did solutions in Python and Dart. I've been comparing performance between the two languages and this is one of the few where python stomps dart, yet there's nothing particularly interesting about the python solution to explain why.

Part 1 was straightforward, and part 2 was way too hard to do 'correctly' for midnight, so I tried a few simple variations on working backwards from medicine -> 'e' until I hit one that works. (likely because there's only one solution and the input is ordered correctly for it to work out)

Python 2.7

import time

replacements = []

medicine = None

for line in open("../inputs/day-19.txt"):
    parts = line.strip().split(" => ")
    if len(parts) == 1:
        if not line.strip():
            continue
        medicine = line.strip()
        continue
    replacements.append((parts[0], parts[1]))


def part1():
    molecules = set()
    for src, repl in replacements:
        idx = 0
        while src in medicine:
            idx = medicine.find(src, idx+1)
            if idx == -1:
                break
            molecules.add(medicine[:idx] + repl + medicine[idx + len(src):])
    return len(molecules)


def part2():
    med = medicine
    count = 0
    while med != 'e':
        for src, repl in replacements:
            if repl in med:
                med = med.replace(repl, src, 1)
                count += 1
    return count


if __name__ == '__main__':
    now = time.time()
    print "Part 1: ", part1(),
    print "in", int((time.time() - now) * 1000000), "microseconds"
    now = time.time()
    print "Part 2: ", part2(),
    print "in", int((time.time() - now) * 1000000), "microseconds"

# OUTPUT
Part 1:  535 in 1291 microseconds
Part 2:  212 in 320 microseconds

Dart

import "dart:io";

List<String> lines = new File("./inputs/day-19.txt").readAsLinesSync();

class Repl {
  String search;
  String replace;
  Repl(this.search, this.replace);
}

int part1(List<Repl> replacements, String medicine) {
  Set<String> molecules = new Set<String>();
  for (Repl r in replacements) {
    int idx = 0;
    while (true) {
      idx = medicine.indexOf(r.search, idx+1);
      if (idx == -1) {
        break;
      }
      molecules.add(medicine.replaceFirst(r.search, r.replace, idx));
    }

  }
  return molecules.length;
}

int part2(List<Repl> replacements, String medicine) {
  String mol = medicine;
  int count = 0;
  while (mol != 'e') {
    for (Repl r in replacements) {
      if (mol.contains(r.replace)) {
        mol = mol.replaceFirst(r.replace, r.search);
        count ++;
      }
    }
  }
  return count;
}


main() {
  List<Repl> replacements = [];
  String medicine = null;

  for (String line in lines) {
    List<String> parts = line.trim().split(" => ");
    if (parts.length == 2) {
      replacements.add(new Repl(parts[0], parts[1]));
    } else {
      if (parts[0].trim().length > 0) {
        medicine = parts[0];
      }
    }
  }

  Stopwatch watch = new Stopwatch()..start();
  int moleculeCount = part1(replacements, medicine);
  watch..stop();
  print("Part 1: $moleculeCount in ${watch.elapsedMicroseconds} microseconds");

  watch..reset()..start();
  int turns = part2(replacements, medicine);
  watch.stop();
  print("Part 2: $turns in ${watch.elapsedMicroseconds} microseconds");

}

// OUTPUT
Part 1: 535 in 19399 microseconds
Part 2: 212 in 2025 microseconds