Mathwords logoMathwords

String (Discrete Math) — Definition, Formula & Examples

A string is a finite, ordered list of symbols written one after another, such as 1011 or cat. A bit string is a string that uses only the symbols 0 and 1.

Let Σ\Sigma be a finite nonempty set called an alphabet. A string (or word) of length nn over Σ\Sigma is a finite sequence w=a1a2⋯anw = a_1a_2\cdots a_n with each ai∈Σa_i \in \Sigma. Equivalently, it is an element of Σn\Sigma^n written without commas or parentheses. Its length is ∣w∣=n|w| = n. The empty string, written λ\lambda or ε\varepsilon, is the unique string of length 00. The set of all strings over Σ\Sigma is Σ∗=⋃n≥0Σn\Sigma^* = \bigcup_{n \ge 0} \Sigma^n. A bit string is a string over Σ={0,1}\Sigma = \{0,1\}.

Key Formula

N=knN = k^{n}
Where:
  • NN = number of distinct strings of length n
  • kk = number of symbols in the alphabet (k = 2 for bit strings)
  • nn = length of each string, a nonnegative integer

How It Works

Two strings are equal only when they have the same length and the same symbol in every position, so order and repetition both matter. You join strings by concatenation: if x=101x = 101 and y=0011y = 0011, then xy=1010011xy = 1010011 and ∣xy∣=∣x∣+∣y∣|xy| = |x| + |y|. Counting problems about strings usually reduce to the product rule, because each position is an independent choice from the alphabet. When a problem fixes some positions or the number of a certain symbol, you count the remaining free choices or use binomial coefficients to pick positions.

Worked Example

Problem: Let w=10110w = 10110 be a bit string and let λ\lambda be the empty string. (a) Find ∣w∣|w|. (b) List all prefixes of ww. (c) Find wλw\lambda. (d) Is 011011 a substring of ww?
Step 1: The length counts the symbols: 1,0,1,1,01, 0, 1, 1, 0.
∣w∣=5|w| = 5
Step 2: A prefix is the first kk symbols, for k=0,1,…,5k = 0, 1, \ldots, 5. The empty string is the prefix with k=0k = 0, so a string of length 5 has 6 prefixes.
λ, 1, 10, 101, 1011, 10110\lambda,\ 1,\ 10,\ 101,\ 1011,\ 10110
Step 3: Concatenating with the empty string adds nothing, so wλ=λw=ww\lambda = \lambda w = w.
wλ=10110,∣wλ∣=5+0=5w\lambda = 10110, \qquad |w\lambda| = 5 + 0 = 5
Step 4: A substring is a block of consecutive symbols. Symbols 2 through 4 of ww are 0,1,10, 1, 1.
w=1 011‾ 0w = 1\,\underline{011}\,0
Answer: ∣w∣=5|w| = 5; the prefixes are λ\lambda, 11, 1010, 101101, 10111011 and 1011010110; wλ=10110w\lambda = 10110; and 011011 is a substring of ww (symbols 2 to 4).

Another Example

Problem: How many strings of length 3 over the alphabet {a,b,c}\{a, b, c\} contain at least one aa?
Step 1: Count all strings of length 3. Each of the 3 positions can hold any of the 3 letters.
33=273^3 = 27
Step 2: Count the strings with no aa: each position holds bb or cc.
23=82^3 = 8
Step 3: Subtract to count the strings with at least one aa.
27−8=1927 - 8 = 19
Answer: There are 19 strings of length 3 over {a,b,c}\{a, b, c\} that contain at least one aa. Counting by positions works for bit strings too: choosing which 3 of 8 positions hold a 1 gives (83)=56\binom{8}{3} = 56 bit strings of length 8 with exactly three 1s.

Why It Matters

Bit strings are the standard model for data in computer science, and counting them is a core skill in a college Discrete Mathematics course. Strings over an alphabet are also the basic objects of formal language and automata theory, where a language is defined as a subset of Σ∗\Sigma^*. Error-correcting codes, binary encodings, and Huffman coding all describe information as bit strings.

Common Mistakes

Mistake: Treating a string like a set, so that 0110 and 1100 are counted as the same, or 0110 is said to have length 2 because it uses only two distinct symbols.
Correction: Order and repetition matter in a string. 0110 and 1100 are different strings, and each has length 4 because length counts positions, not distinct symbols.
Mistake: Treating a bit string as a binary number, so that 0011 is considered equal to 11, or forgetting the empty string when counting strings of length at most nn.
Correction: Leading zeros are part of the string: 0011 has length 4 and 11 has length 2, so they are different strings. When lengths start at 0, include the empty string, which contributes 20=12^0 = 1.

Related Terms