Strings, Characters and ASCII

Functions and Data Containers · 30 min

Foundations · Strings & characters

A string is characters in numbered slots

Index it like an array, because it is one. Every character in it is a number underneath, and that one fact turns case conversion, digit parsing and vowel checks into arithmetic.

Walk RECURSION one character at a time →
"RECURSION"nine characters stored one after another
→
slots 0 … 8every character sits at a numbered index
→
s[1] is 'E'indexing hands back exactly one character
→
'E' is 69and that character is really a small number

01 The idea

One row of characters, numbered from zero

A string is text to you. To the machine it is a row of slots, one character per slot, numbered from 0. The word RECURSION is nine slots: slot 0 holds R, slot 1 holds E, slot 8 holds N. You read a slot with s[0], s[1], s[8] — the same square brackets you use on an array, because underneath it is an array.

A slot does not hold a letter shape either. It holds a small whole number: the character’s code. In ASCII, capital A is 65, so B is 66 and Z is 90. Small a is 97, so the same letter in the other case is exactly 32 higher. The codes inside each block run consecutively with no gaps, and that is what lets you do arithmetic on characters — c - 'A' turns a capital letter into its position 0 to 25, and c - '0' turns the character 7 into the number seven.

Walk one index from 0 to length − 1, look at the single character it points at, and decide. Counting, searching, reversing and checking a palindrome are all that same walk with a different decision inside.
CharacterOne slot’s worth of text — a single letter, digit, space or symbol. It is stored as a number, not as a shape.
ASCII codeThe number a character is stored as. 'A' is 65, 'a' is 97, '0' is 48, a space is 32. A to Z run consecutively, which is what makes character arithmetic work.
IndexThe slot number, counting from 0. A string of length n has valid indices 0 to n − 1. Reading s[n] is off the end: Java and Python raise an exception, JavaScript quietly returns undefined. Never a usable character.

02 Worked example

Counting the vowels in RECURSION

Take RECURSION and count its vowels by hand, one slot at a time. One index walks from 0 to 8. At each stop you look at exactly one character and ask one question: is it A, E, I, O or U? A green cell means counted, a rose cell means checked and skipped, and the running count is on the right.

slot012345678nine slots, numbered from zero
i = 0RECURSIONR is not a vowel → count stays 0
i = 1RECURSIONE is a vowel → count = 1
i = 2RECURSIONC is not a vowel → count stays 1
i = 3RECURSIONU is a vowel → count = 2
i = 4RECURSIONR is not a vowel → count stays 2
i = 5RECURSIONS is not a vowel → count stays 2
i = 6RECURSIONI is a vowel → count = 3
i = 7RECURSIONO is a vowel → count = 4
i = 8RECURSIONN is not a vowel → count stays 4
resultRECURSION4 vowels: E U I O, at slots 1 3 6 7

Nine stops, nine questions, one number at the end: 4. Notice what the walk never needed. It never looked back, never looked ahead, and never held more than one character at a time — so it costs O(n) time and O(1) extra space. Change the question at each stop from “is it a vowel” to “does it match the letter I am hunting for” and you have written linear search over a string without changing a single line of the loop.

03 Mechanics

Reversing a string, and what immutability costs

Now the half that catches people out. In Java, Python, C# and JavaScript a string cannot be changed after it is made — s.toUpperCase() does not modify s, it hands you a brand-new string. So reversing RECURSION into NOISRUCER means building something new. Both versions below walk the same nine slots from 8 down to 0. Only the writing differs, and the difference is not cosmetic.

Naive — glue a new string each turn

result = ""for i = length(s) - 1 down to 0:    result = result + s[i]  // a NEW stringreturn result

Builder — one buffer, filled in place

b = new builder()for i = length(s) - 1 down to 0:    b.append(s[i])       // no copyreturn b.toString()

The assignment on line 3 was hiding an allocation. result = result + s[i] cannot extend result, because a string can never be extended. It allocates a fresh string one character longer and copies everything across. Turn k copies k characters, so the nine turns copy 1 + 2 + … + 9 = 45 characters to produce a 9-character answer.

The builder owns a buffer it is allowed to overwrite. append writes one character into spare capacity and moves a length marker — no copy, no new object. Nine appends cost nine writes, so the reverse drops from O(n²) to O(n). At 1,000 characters that is 1,000 writes instead of 500,500.

Neither version touched s. That is not politeness, it is the rule: the original string is unreachable for writing. If your language hands you a mutable character array instead, you can go further and swap the ends inwards — 0 with 8, 1 with 7, 2 with 6, 3 with 5, leaving slot 4 alone. Four swaps, no new memory at all.

05 Cheat sheet

The string operations you will be asked to cost

OperationCostWhat catches people out
Read one character, s[i]O(1)Valid indices are 0 to n − 1. s[n] is off the end: an exception in Java and Python, undefined in JavaScript, the NUL terminator in C. Never a usable character.
Length of a stringO(1)Stored with the data in Java and Python. C keeps no length field, so strlen walks to the terminator and costs O(n).
Join two strings, s + tO(n + m)Always allocates a new string and copies both. Harmless once, ruinous in a loop.
s = s + c inside a loopO(n²)Each turn copies the whole prefix again — 45 character copies to build our 9-character reversal.
Builder append(c)O(1)Amortised: the buffer doubles when it fills. Nothing is a real string until you call toString or join.
substring(a, b)O(b − a)The end index is exclusive. substring(0, 3) of RECURSION is REC, not RECU.
s == t in JavaO(1)Compares addresses, not characters. Use equals; when == works it is an accident of the literal pool.
Find a substring, indexOf(t)O(n × m)The plain scan retries the whole pattern at every start position. KMP is the linear answer.
Codes are contiguous inside a block'A' to 'Z' is 65 to 90, 'a' to 'z' is 97 to 122, '0' to '9' is 48 to 57. So c - '0' gives a digit’s value, c - 'A' gives a letter’s position 0 to 25, and 'a' - 'A' is exactly 32.
A method call is not a changetoUpperCase, trim and replace all return a new string and leave the original alone. Calling one and not assigning the result is the most common beginner bug in string code.
ASCII is 128 codes; text is biggerASCII is 7 bits, values 0 to 127. Anything past that — é, ₹, an emoji — is Unicode, and one character can take several bytes or two UTF-16 units. Byte length and character count stop agreeing there.

06 Where & why

Concatenation is not slow. Concatenation in a loop is.

Every language gives you + for strings and most of the time it is the right tool. What makes it dangerous is that the copy it performs is invisible in the source, so the cost only surfaces once the loop count grows. Here is where each option belongs.

Reach for plain concatenation when…

You are joining a fixed number of piecesThree or four fragments in one expression is one allocation, and most compilers fold it into a single builder for you anyway.
The loop count is bounded and tinyBuilding a 10-character key copies 55 characters in total. Below a few hundred the copying is invisible next to everything else the code does.
The value has to be sharedAn immutable string can be handed to any function, cached, or used as a map key with no defensive copy, because nobody can alter it behind your back.
The result is the final answerNothing more will be appended, so a builder buys you nothing and costs an extra conversion at the end.

Use something else when…

SituationBetter choiceWhy
You are assembling text inside a loopStringBuilder, or a list plus joinConcatenation recopies the whole prefix every turn: O(n²) writes against O(n) for the builder.
You need to change characters in placeA character array — char[] or list(s)Strings cannot be written to at all. Convert once, mutate freely, convert back: two O(n) passes instead of n allocations.
You are gluing a list together with a separatorjoinOne pass, one allocation, and it handles the trailing separator that hand-written loops always get wrong.
The text is not plain EnglishUnicode-aware APIsIndexing by byte or by UTF-16 unit can split a character in half. An accented letter or an emoji is not one code unit.
Assemble with a builder, then freeze into a string once. And when a question says “reverse it in place”, it is quietly telling you the input is a character array — because a string cannot be changed in place at all.

07 Interview questions

What they actually ask

Strings open almost every coding round, and the follow-up is always about cost. Know why concatenation in a loop is quadratic and you have answered half of these before they are asked.

What is the difference between a character and a string?
A character is one slot: a single letter, digit or symbol, stored as a small whole number. A string is a sequence of those slots with a length, indexed from 0 exactly like an array. In C a string literally is a char array ending in a NUL byte; in Java and Python it is an object wrapping one that also knows its own length.
What is ASCII, and why does character arithmetic work?
ASCII maps 128 characters onto the numbers 0 to 127 — A is 65, a is 97, 0 is 48 and a space is 32. Arithmetic works because the codes inside each block are consecutive with no gaps: A to Z run 65 to 90. So c - '0' converts a digit character into its value, and c - 'A' gives a capital letter’s position from 0 to 25.
How do you flip a letter’s case without a library call?
Add or subtract 32, because 'a' - 'A' is exactly 32. c + 32 makes a capital lowercase and c - 32 does the reverse, and since 32 is a single bit you can write c | 32 and c & ~32 instead. Range-check first: it is only correct for ASCII letters, and applied to a digit or symbol it silently produces nonsense.
What does it mean that strings are immutable?
Once a string exists its characters can never be changed. Everything that looks like an edit — toUpperCase, replace, trim, + — builds and returns a new string and leaves the original untouched. That is why s.toUpperCase(); on a line of its own does nothing at all: you have to assign the result back.
Why is building a string in a loop O(n²)?
Because s = s + c cannot extend s; it allocates a new string one character longer and copies the whole prefix into it. Turn k copies k characters, so n turns copy 1 + 2 + … + n = n(n+1)/2 characters. Reversing our nine-letter word that way copies 45 characters to produce 9; at 1,000 characters it is 500,500.
String versus StringBuilder versus StringBuffer?
String is immutable, so every edit allocates and copies. StringBuilder wraps a growable character buffer you can append to in O(1) amortised time, which is what you use to assemble text in a loop. StringBuffer is the same class with every method synchronised — slower, and only worth it when two threads genuinely append to one buffer.
How do you reverse a string in place?
Strictly you cannot, because a string is immutable — “in place” means you were handed a character array. Then it is two indices: swap slot 0 with the last, step both inwards, and stop when they meet. For nine characters that is four swaps with slot 4 left alone, so O(n) time and O(1) extra space.
Why does == sometimes work on Java strings and sometimes not?
Because == compares references, not characters. Identical literals are interned into one shared pool object, so comparing two literals happens to come out true — but new String("abc") against the literal is false, and so is any string built at runtime by concatenation or read from input. Always use equals; the cases where == works are an accident of the pool.
How would you check whether a string is a palindrome?
Put one index at 0 and one at n - 1, compare the two characters, and step both inwards until they cross. Any mismatch answers no, and surviving to the middle answers yes, in O(n) time and O(1) space. Say why you did not build reverse(s) and compare: that is the same O(n) time but allocates a second string, and it always does the full n characters of work, while two indices can quit on the very first mismatch. Odd and even lengths need no special case — the indices either land on the same slot or step past each other.
Is finding a string’s length always O(1)?
In Java and Python yes — the length is stored with the data, so reading it is a field access. In C there is no length field: strlen walks the array to the NUL terminator, so it costs O(n). That matters because for (i = 0; i < strlen(s); i++) recomputes it on every turn and quietly turns an O(n) loop into an O(n²) one.
Does one character always mean one byte?
Only inside ASCII. Anything above code 127 is Unicode: in UTF-8 an accented letter takes 2 bytes and an emoji takes 4, and Java’s length() counts UTF-16 units so an emoji counts as 2. Byte length, code-unit length and the number of characters a human sees are three different numbers, so say which one you mean.
Where would you actually use character arithmetic?
Any time a character has to index something, or has to be shifted by a fixed distance. Indexing is the common case: c - 'a' always lands in 0 to 25, so a plain 26-slot array replaces a hash map for anything letter-shaped, and the table is a constant size no matter how long the text is. Shifting is the other case — a Caesar or ROT13 cipher is (c - 'a' + k) % 26 + 'a', which wraps z round to a without a single if. Hex decoding is the same idea across two ranges: c - '0' for a digit and c - 'A' + 10 for A to F.

08 Practice problems

Six walks to do by hand first

For each one, write the slot numbers in a row and decide what the single question at each stop is. If you cannot say what one stop does, the loop will not rescue you.

Vowels, consonants and neither

Easy
Given a line of text, return three counts: vowels, consonants, and characters that are neither.
Follow-up
The input now holds spaces, digits and punctuation, so “not a vowel” and “consonant” stop meaning the same thing.
Show the hint
Ask two questions per stop, in order: is this character a letter at all, and only then is it a vowel.

Longest run of one character

Easy
Return the length of the longest stretch of one character repeated back to back: in aaabbbbcc the answer is 4, and in abcde it is 1.
Follow-up
A run ends when the character changes — but the last run ends because the string ran out, so it never gets a closing comparison and it is the one people lose.
Show the hint
Carry two numbers as the index walks: how long the run you are currently inside is, and the best length seen so far. Comparing s[i] with s[i-1] tells you whether to extend or restart — then work out where the best has to be updated so that a run touching the final slot still counts.

Palindrome with junk in it

Medium
Return true if the text reads the same forwards and backwards once case is ignored and every non-letter is skipped.
Follow-up
You are not allowed to build a cleaned copy first, so the two indices must step over the junk as they walk and the extra space must stay O(1).
Show the hint
Before each comparison, advance the left index while it points at a non-letter and pull the right index back while it points at a non-letter.

Reverse the words, not the letters

Medium
Given a sentence, return it with the word order reversed: the sky is blue becomes blue is sky the.
Follow-up
Reversing the whole string reverses every word too, so one pass is not enough — you have to undo something you just did.
Show the hint
Reverse the whole character array first and read what comes out: the word order is now right, but every individual word is spelled backwards. That leftover damage is a separate and much smaller job, and section 03 already showed you how to reverse a span in place — you only have to find where each span starts and ends.

First non-repeating character

Medium
Return the first character in the string that appears exactly once, or a marker value if every character repeats.
Follow-up
One walk cannot answer it — you need every count before you can judge the first slot, but the answer is first by position, not first by count.
Show the hint
For lowercase letters, keep an array of 26 counts indexed by c - 'a'. Walk once to fill it, then walk again and return the first character whose count is 1.

Turn a string into a number

Hard
Implement atoi: read an optional leading + or -, then consume digits and return the integer they represent, stopping at the first character that is not a digit.
Follow-up
Character arithmetic now builds a value instead of just testing one, and a long input can overflow a 32-bit integer — so the check has to happen before the multiply, not after.
Show the hint
Each digit is c - '0' and the running value is value = value * 10 + digit. Before multiplying, compare value against the limit divided by 10 to see whether the next step would overflow.