This is more efficient but still hard to read.  You see a lot of duplication in this code.  Also lines should be at most 80 chars long (easier to read, display fine on any device).  What about something like:
```ocaml
let string_of_state {d; f; pred; color} =
  let open Printf in
  let bindings m fmt =
    let b = Char_map.bindings m in
    String.concat ", " (List.map (fun (x,y) -> sprintf fmt x y) b) in
  sprintf " d = {%s}\n f = {%s}\n pred = {%s}\n"
          (bindings d "'%c':'%d'") (bindings f "'%c':'%d'")
          (bindings pred "'%c':'%c'")
```