What Does This Program Do? - Strings

Contest 4 WDTPD problems use strings. You’ll trace programs that slice, build, and compare strings using loops and conditionals. The main challenge is keeping track of indices - strings are zero-indexed in ACSL.

ACSL pseudocode reference

The pseudocode used in ACSL problems supports the following:

Operators (in precedence order): ! (not), ^ or ↑ (exponent), *, /, %, +, -, >, <, >=, <=, !=, ==, &&, ||

Built-in functions: abs(x), sqrt(x), int(x) (greatest integer ≤ x)

Control flow:

IF boolean THEN
    statements
ELSE
    statements
END IF

WHILE boolean
    statements
END WHILE

FOR variable = start TO end STEP increment
    statements
NEXT variable

Multiple statements on one line are separated by a colon: num = 0; t = ""

String operations

Length

len("HELLO") = 5

An empty string "" has length 0. Accessing an index at a negative position or at a position equal to or greater than the length causes an error.

Indexing (zero-based)

S = "COMPUTER"
S[0] = "C"
S[3] = "P"
S[7] = "R"

The last valid index is len(S) - 1.

Substring

ACSL pseudocode has three slice forms. They do not follow Python semantics.

S[:n] returns the first n characters:

S = "COMPUTER"
S[:3] = "COM"   (first 3 chars, indices 0-2)

S[n:] returns the last n characters:

S = "COMPUTER"
S[3:] = "TER"   (last 3 chars)

S[i:j] returns characters from index i to index j, inclusive of both endpoints:

S = "COMPUTER"
S[2:5] = "MPUT"  (indices 2, 3, 4, 5)

Official ACSL example: For S = "ACSL WDTPD" (length 10):

• S[:3] = "ACS" (first 3 chars)
• S[4:] = "DTPD" (last 4 chars)
• S[2:6] = "SL WD" (indices 2 through 6 inclusive)

Critical difference from Python: In Python, S[n:] means “from index n to end” and S[i:j] excludes index j. In ACSL, S[n:] means “last n characters” and S[i:j] includes index j. Mixing these up will give wrong answers.

Concatenation

"HELLO" + " " + "WORLD" = "HELLO WORLD"

The + operator joins strings end to end.

Try it: trace a string program

Watch how the string variable changes step by step.

1S = "ACSL"2R = ""3FOR i = len(S)-1 TO 0 STEP -14    R = R + S[i]5NEXT i6OUTPUT R

String tracing strategy

For string problems, keep a table showing the value of each string variable after every operation.

Example:

S = "PROGRAMMING"
T = ""
FOR i = 0 TO len(S) - 1
    IF S[i] == "G" OR S[i] == "M" THEN
        T = T + S[i]
    END IF
NEXT i
OUTPUT T

Walk through each character:

• P: no
• R: no
• O: no
• G: yes, T = “G”
• R: no
• A: no
• M: yes, T = “GM”
• M: yes, T = “GMM”
• I: no
• N: no
• G: yes, T = “GMMG”

Answer: GMMG

Common string patterns in ACSL

Pattern 1: Reversing a string

S = "ACSL"
R = ""
FOR i = len(S) - 1 TO 0 STEP -1
    R = R + S[i]
NEXT i
OUTPUT R

Builds backwards by prepending one character per iteration: L, LC, LCS, LCSA.

Answer: LCSA

Pattern 2: Character replacement

S = "HELLO WORLD"
T = ""
FOR i = 0 TO len(S) - 1
    IF S[i] == " " THEN
        T = T + "-"
    ELSE
        T = T + S[i]
    END IF
NEXT i
OUTPUT T

Answer: HELLO-WORLD

Pattern 3: Counting characters

S = "MISSISSIPPI"
count = 0
FOR i = 0 TO len(S) - 1
    IF S[i] == "S" THEN
        count = count + 1
    END IF
NEXT i
OUTPUT count

Answer: 4

Pattern 4: Palindrome check

S = "RACECAR"
result = 1
FOR i = 0 TO int(len(S) / 2) - 1
    IF S[i] != S[len(S) - 1 - i] THEN
        result = 0
    END IF
NEXT i
OUTPUT result

Compares first and last characters, working inward. Only needs to check int(len(S) / 2) pairs.

Answer: 1

Pattern 5: Comparing two strings

From official ACSL sample problem:

a = "BANANAS"
num = 0; t = ""
FOR j = len(a)-1 TO 0 STEP -1
    t = t + a[j]
NEXT j
FOR j = 0 TO len(a) - 1
    IF a[j] == t[j] THEN
        num = num + 1
    END IF
NEXT j
OUTPUT num

Step 1: build t = reverse of a = "SANANAB"

Step 2: compare each position:

Answer: 5

Common mistakes

1. Off-by-one with zero indexing. S = "CAT" has valid indices 0, 1, 2. S[3] is an error.
2. Substring end index is inclusive. S[1:3] gives 3 characters (indices 1, 2, 3). Also, S[n:] means the last n characters, not “from index n.”
3. Concatenation order. T = T + S[i] appends to the end. T = S[i] + T prepends to the beginning. The order determines whether you build a forward or reverse string.
4. FOR loop direction. To iterate backwards, you must include STEP -1. Without it, the loop body never executes when start > end.

Contest strategy

• Write the string with index numbers above each character before tracing
• For build-a-string problems, track the string variable in a column of your trace table
• For comparison problems (like palindromes), trace both strings side by side
• Typical time: 90-120 seconds per problem