If the numbers 1 - 100 are written in one long string, how many substrings of minimum length 2 can be found with strictly decreasing numbers? e.g. 12345678910 has three such substrings: 91, 910, 10.

CLS
FOR i = 1 TO 100
  s$ = s$ + LTRIM$(STR$(i))
NEXT
PRINT LEN(s$), s$

FOR i = 2 TO LEN(s$)
 IF MID$(s$, i, 1) < MID$(s$, i - 1, 1) THEN
  IF lCt = 0 THEN
   lCt = 2
  ELSE
   lCt = lCt + 1
  END IF
 ELSE
  IF lCt > 0 THEN
   PRINT MID$(s$, i - lCt, lCt); "  ";
   totStr(lCt) = totStr(lCt) + 1
   lCt = 0
  END IF
 END IF
NEXT
IF lCt > 0 THEN
 PRINT MID$(s$, i - lCt, lCt); "  ";
 totStr(lCt) = totStr(lCt) + 1
 lCt = 0
END IF

PRINT : PRINT
FOR i = 0 TO 9
 PRINT totStr(i);
NEXT
PRINT

finds substrings of various lengths without counting lower levels of substring (that is, a length-3 substring counts only as itself, and the two length-2's within it aren't counted).

What it finds are 65 of length 2 and 9 of length 3. But the length-3 substrings count for a total of three substrings each--the length-3 substring itself and two length-2 substrings.  So the total is 65 + 3*9 = 92.

With the above result completed, it's easier to retrofit an "analytic" solution:

Length-3 strings:

At 9-10, 19-20, 29-30, ... , 99-100 (but with 89-90 excluded); so that's 10 - 1 = 9.

Length-2 strings not within length-3:

Teens: 12-13, ... , 18-19; Count: 7
20's: 23-24, ... , 28-29; Count: 6
      21; Count 1
30's: 34-35, ... , 38-39; Count: 5
      31, 32; Count 2
...
80's: 81, ... , 87; Count 7
90's: 90 (as 89-90 wasn't counted already), 91, ... , 98; Count 9.

The teens through 80's count for 7 each, totalling 56. The nine from the 90's bring this to 65.

Then the 65 doubles and nine triples are combined as before: 65 + 3*9 = 92.

Posted by Charlie on 2010-07-27 13:59:29