What Does This Program Do? - Strings

Contest 4 adds string manipulation to WDTPD problems. You’ll trace programs that slice, search, concatenate, and transform strings. The main challenge is keeping track of indices - strings are zero-indexed in ACSL, just like arrays.

ACSL string operations

ACSL pseudocode uses these string functions. Memorize them - they appear in almost every problem.

Length

len("HELLO") = 5

Returns the number of characters.

Indexing (zero-based)

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

Watch out: The last valid index is $len (S) - 1$ , not $len (S)$ .

Substring

S = "COMPUTER"
S[2:5] = "MPU"

S[start:end] returns characters from index start up to but not including end. This is the same convention as Python slicing.

S[0:3] = “COM” (indices 0, 1, 2)
S[5:] = “TER” (index 5 to end)
S[:4] = “COMP” (start to index 3)

Concatenation

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

The + operator joins strings end to end.

Find / Index

S = "BANANA"
find(S, "AN") = 1

Returns the index of the first occurrence of the substring. Returns -1 if not found.

ASCII values

ACSL problems sometimes use $ord ()$ and $chr ()$ :

$ord ("A") = 65$
$chr (65) = "A"$
$ord ("a") = 97$
$ord ("0") = 48$

Key ranges:

Uppercase A-Z: $65$ - $90$
Lowercase a-z: $97$ - $122$
Digits 0-9: $48$ - $57$

Useful trick: $ord (c h) - ord ("A")$ gives the position of an uppercase letter ( $A = 0, B = 1, \dots, Z = 25$ ).

Try it: trace a string program

Watch how the string variable changes as operations are applied.

Code

1S = "HELLO"2S = REVERSE(S)3x = LEN(S)4c = S[0]5OUTPUT: c, x

Variables

Name	Value
S	"HELLO"

Step 1 of 5

String tracing strategy

For string problems, keep a string state 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
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

Speed tip: For filtering problems like this, just scan the string for matching characters instead of tracing every iteration.

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
OUTPUT: R

Builds the string backwards: L, then LS, then LSC, then LSCA.

Answer: LSCA

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
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
OUTPUT: count

Answer: 4 (S appears at indices $2, 3, 5, 6$ )

Pattern 4: Case conversion using ASCII

S = "Hello"
T = ""
FOR i = 0 TO len(S) - 1
    c = ord(S[i])
    IF c >= 97 AND c <= 122 THEN
        T = T + chr(c - 32)
    ELSE
        T = T + S[i]
    END IF
NEXT
OUTPUT: T

This converts lowercase to uppercase. The difference between ‘a’ ( $97$ ) and ‘A’ ( $65$ ) is $32$ .

Answer: HELLO

Pattern 5: Palindrome check

S = "RACECAR"
is_palindrome = true
FOR i = 0 TO INT(len(S) / 2) - 1
    IF S[i] != S[len(S) - 1 - i] THEN
        is_palindrome = false
    END IF
NEXT
OUTPUT: is_palindrome

Compares: R=R, A=A, C=C. Only needs to check $INT (len (S) /2)$ characters. All match.

Answer: true

Pattern 6: Building a string by index mapping

S = "COMPUTER"
idx = [3, 0, 7, 4, 1, 5, 2, 6]
T = ""
FOR i = 0 TO 7
    T = T + S[idx[i]]
NEXT
OUTPUT: T

$i$	$idx [i]$	$S [idx [i]]$	T
$0$	$3$	P	P
$1$	$0$	C	PC
$2$	$7$	R	PCR
$3$	$4$	U	PCRU
$4$	$1$	O	PCRUO
$5$	$5$	T	PCRUOT
$6$	$2$	M	PCRUOTM
$7$	$6$	E	PCRUOTME

Answer: PCRUOTME

This is an anagram/permutation of the original string.

Pattern 7: Extracting words

S = "THE QUICK FOX"
words = 1
FOR i = 0 TO len(S) - 1
    IF S[i] == " " THEN
        words = words + 1
    END IF
NEXT
OUTPUT: words

Answer: 3 (two spaces = three words)

String + array combinations

Contest 4 problems often combine strings and arrays. A common pattern is treating a string as an array of characters.

Example: Caesar cipher

S = "HELLO"
shift = 3
T = ""
FOR i = 0 TO len(S) - 1
    c = ord(S[i]) - ord("A")
    c = (c + shift) MOD 26
    T = T + chr(c + ord("A"))
NEXT
OUTPUT: T

$i$	$S [i]$	$c$ (position)	$c + 3$	$mod 26$	$chr$	T
$0$	H	$7$	$10$	$10$	K	K
$1$	E	$4$	$7$	$7$	H	KH
$2$	L	$11$	$14$	$14$	O	KHO
$3$	L	$11$	$14$	$14$	O	KHOO
$4$	O	$14$	$17$	$17$	R	KHOOR

Answer: KHOOR

The $mod 26$ handles wrap-around (Z + 1 = A).

Common mistakes

Off-by-one with zero indexing. S = "CAT" has characters at indices $0, 1, 2$ . S[3] is out of bounds.
Substring end index is exclusive. S[1:3] gives $2$ characters (at indices $1$ and $2$ ), not $3$ .
Forgetting string immutability. In most pseudocode, you build a new string - you can’t change a character in place. S[0] = "X" is not usually valid.
ASCII arithmetic errors. Remember: $A = 65$ , $a = 97$ , $0 = 48$ . The gap between uppercase and lowercase is $32$ .
Concatenation order. T = T + S[i] appends to the end. T = S[i] + T prepends to the beginning. The order matters for building reversed or shifted strings.

Contest strategy

Write out the string with index numbers above each character for quick reference
For filtering/building problems, scan for the pattern rather than tracing every iteration
For ASCII problems, write out the key values: $A = 65$ , $Z = 90$ , $a = 97$ , $space = 32$
When combining strings with arrays/loops, use a table tracking both the string being built and any numeric variables
Typical time: 90-120 seconds per problem