String pattern defined by number of characters

Question

I want to extract non-overlapping substrings from strings with only four possible characters a,b,c,d. These strings will always have equally many "a" and "d" characters. The substrings x I want satisy the following criteria:

1. x starts with an "a" and ends with a "d", or is an "isolated" "b" or "c", see below.
2. x has equally many "a"'s and "d"'s.
3. Any substring of x starting at the first "a" has more "a"s than, or equally many "a"'s as, "d"'s.

For instance, the substrings I'm looking for in "abdcbaacdabbdd" are:

• "abd"
• "c"
• "b"
• "aacdabbdd"

I have made a working code doing this iteratively:

pick[i_]:=(Which[
occ[[i]]=="a",If[trigger++==0,startpos=i],
occ[[i]]=="d",If[--trigger==0,Sow[occ[[startpos;;i]]]],
trigger==0,Sow[{occ[[i]]}];
];
i+1);

subStrings[s_String]:=
Block[
{trigger=0,startpos,occ=Characters[s]},
Reap[Nest[pick,1,Length[occ]]][[2,1]]
]

but I would like to know if there is an easy way to do this using string patterns.

Answer 1

The rules seem to be amenable to a recursive regular expression:

extract[s_] := StringCases[s, RegularExpression["b|c|(a(?R)*d)"]]

extract["abdcbaacdabbdd"]
(* {"abd", "c", "b", "aacdabbdd"} *)

Further examples:

extract["b"]                     (* {"b"} *)
extract["bcbbc"]                 (* {"b", "c", "b", "b", "c"} *)
extract["ad"]                    (* {"ad"} *)
extract["abcd"]                  (* {"abcd"} *)
extract["aadd"]                  (* {"aadd"} *)
extract["aabcddaaabcabdbdd"]     (* {"aabcdd", "aabcabdbdd"} *)
extract["adabdaabcdddaaabbbdd"]  (* {"ad", "abd", "aabcdd", "aabbbdd"} *)
extract["aabdacdd"]              (* {"aabdacdd"} *)

Recursive Patterns: Meaning of (?R)

Mathematica uses the PCRE regular expression engine internally. (?R) is an example of a PCRE recursive pattern -- look for the section labelled "RECURSIVE PATTERNS" in the PCRE documentation. (?R) is a reference to the entire pattern being matched. Be careful to distinguish that this is a reference to the pattern itself, not to the characters matched by the pattern. Thus, the pattern will match "b", "c", or "a...d", where "..." is valid match in its own right according to the whole pattern.

A recursive reference need not refer to the entire pattern. For example, (?1) in the regular expression "b|c|(a((?1)|.)*?d)" refers to the first parenthesized pattern, namely (a((?1)|.)*?d). This permits greater flexibility should it be discovered that the original proposal misses some corner cases.

Answer 2

I was able to match your example, but I'm not sure I completely grasped the problem!

exampleStr = "abdcbaacdabbdd"

checkSubStr[str_String] := 
 And @@ ((Count[Take[Characters@str, #], "a"] >=  Count[Take[Characters@str, #], "d"]) & /@ Range[StringLength@str])

StringCases[exampleStr, 
 Shortest@ tot : ("b" | "c" | (x : ("a" ~~ ___ ~~ "d")) /; 
      And[Count[Characters@x, "a"] == Count[Characters@x, "d"], checkSubStr@x]) :> tot
, Overlaps -> False]

{"abd", "c", "b", "aacdabbdd"}

Answer 3

Not anyhere elegant as the OP's own method, but ... staying in the String universe may be a good alternative.

Stealing @Aisamu's string pattern and using only String functions:

ClearAll[cssF, strngCF];
cssF = Function[{s}, And @@ Flatten[{Equal @@ (StringCount[s, #] & /@ {"a", "d"}),
                     (StringCount[#, "a"] >= StringCount[#, "d"] & /@
                            (StringTake[s, #] & /@ Range[-1 + Length@s]))}]];

strngCF = StringCases[#, Shortest@ p: ("b" | "c" | (p2 : ("a" ~~ ___ ~~ "d")) /; cssF[p2]) :> p] &;

Examples:

strngCF@"abdcbaacdabbdd"  (* OP's example *)
(* {"abd","c","b","aacdabbdd"} *)

strngCF@"adadacbcdacdcadbacbd"
(* {"ad","ad","acbcd","acd","c","ad","b","acbd"} *)

strngCF@ "dacacbddaaaacdcdccdd"
(* {"acacbdd","aaaacdcdccdd"} *)