First and Last Positions of Every Character

A repeated character has two different boundary positions

For the string "banana", the answer for each present character is a pair of positions. Character a first appears at index 1 and last appears at index 5, so its pair is (1, 5). Character n has pair (2, 4), and character b has pair (0, 0). These numbers are positions in the string, not occurrence counts. The character a occurs three times, but its answer is still about where its first and last occurrences sit.

A character that appears once has equal boundaries. That is why b has first index 0 and last index 0. Equal values do not mean the character was missed, and they do not mean the answer stores a count. They mean the only occurrence was at index 0.

The value -1 distinguishes an unseen character from one found at index 0

Use two tables indexed by ASCII value: first[c] stores the first index seen for character c, and last[c] stores the most recent index seen. Before scanning "banana", initialize every entry in both tables to -1. This sentinel value means that no occurrence has been recorded yet.

int first[128];
int last[128];

for (int c = 0; c < 128; c++) {
    first[c] = -1;
    last[c] = -1;
}

Zero cannot mean unseen because index 0 is a valid position. The character b is found at index 0, so after processing it, first['b'] and last['b'] must both be 0. If zero were also the marker for an unseen character, the algorithm could not tell b apart from a character that had never appeared.

One left-to-right scan needs two different update rules

At index i, let c be the character at that position. Set first[c] to i only if first[c] is still -1. Then set last[c] to i every time. The first rule protects the earliest occurrence, while the second rule allows the newest occurrence to become the last one.

for (int i = 0; i < 6; i++) {
    char c = "banana"[i];

    if (first[c] == -1) {
        first[c] = i;
    }
    last[c] = i;
}

When the scan reaches a at index 3, first['a'] is already 1, so the condition is false and that value stays unchanged. The unconditional assignment still changes last['a'] to 3. At index 5, the same pattern changes last['a'] to 5 while first['a'] remains 1.

first[c] = i;

Printing only initialized entries produces one result per present character

After the scan, walk through the ASCII table from its smallest value to its largest. Print a character only when first[c] is not -1. For "banana", the initialized entries are a, b, and n, so the output is in ASCII order even though b was encountered before a during the string scan.

a 1 5
b 0 0
n 2 4

The condition first[c] != -1 prevents characters absent from "banana" from being printed. Their first and last entries are still -1, so they remain distinguishable from b, whose two entries are both 0.

The scan of the string visits each of its characters once, so it takes linear time in the string length. The ASCII-table scan checks a fixed number of entries, and the two tables also have fixed size, so that work and storage are constant with respect to the string length.