Problem

Given a string, find the last character that does not repeat anywhere else in the string (ignoring spaces). If no such character exists, return a suitable message.

Examples

Example 1

1
2
3
4

Input:
str = "algorithms tutorials"
Output: 'u'
Explanation: 'u' is the last character (from right) that appears only once.

Example 2

1
2
3
4

Input:
str = "aabbccdd"
Output: No non-repeating character found.
Explanation: Every character repeats.

Solution

Method 1 – Naive Double Loop

Intuition

Check each character from right to left, and for each, scan the rest of the string to see if it repeats.

Approach

  1. Iterate the string from right to left.
  2. For each character, check if it appears elsewhere in the string.
  3. Return the first such character found.
  4. If none found, return a suitable message.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
  char lastNonRepeatingChar(const string& s) {
    for (int i = s.size() - 1; i >= 0; --i) {
      if (s[i] == ' ') continue;
      bool unique = true;
      for (int j = 0; j < s.size(); ++j) {
        if (i != j && s[i] == s[j]) { unique = false; break; }
      }
      if (unique) return s[i];
    }
    return '\0'; // or throw/return special value
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func lastNonRepeatingChar(s string) byte {
  for i := len(s) - 1; i >= 0; i-- {
    if s[i] == ' ' { continue }
    unique := true
    for j := 0; j < len(s); j++ {
      if i != j && s[i] == s[j] { unique = false; break }
    }
    if unique { return s[i] }
  }
  return 0
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
  public Character lastNonRepeatingChar(String s) {
    for (int i = s.length() - 1; i >= 0; i--) {
      if (s.charAt(i) == ' ') continue;
      boolean unique = true;
      for (int j = 0; j < s.length(); j++) {
        if (i != j && s.charAt(i) == s.charAt(j)) { unique = false; break; }
      }
      if (unique) return s.charAt(i);
    }
    return null;
  }
}
1
2
3
4
5
6
7

class Solution:
  def last_non_repeating_char(self, s: str) -> str | None:
    for i in range(len(s) - 1, -1, -1):
      if s[i] == ' ': continue
      if s.count(s[i]) == 1:
        return s[i]
    return None

Complexity

  • ⏰ Time complexity: O(n^2), since for each character, we may scan the whole string.
  • 🧺 Space complexity: O(1), no extra space beyond variables.

Method 2 – Hash Map for Counting

Intuition

Count the occurrences of each character, then scan from right to left to find the last character with count 1.

Approach

  1. Remove spaces from the string.
  2. Count occurrences of each character using a hash map.
  3. Iterate from right to left, return the first character with count 1.
  4. If none found, return a suitable message.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include <unordered_map>
class Solution {
public:
  char lastNonRepeatingChar(const string& s) {
    unordered_map<char, int> cnt;
    for (char c : s) if (c != ' ') cnt[c]++;
    for (int i = s.size() - 1; i >= 0; --i) {
      if (s[i] != ' ' && cnt[s[i]] == 1) return s[i];
    }
    return '\0';
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func lastNonRepeatingChar(s string) byte {
  cnt := map[byte]int{}
  for i := 0; i < len(s); i++ {
    if s[i] != ' ' { cnt[s[i]]++ }
  }
  for i := len(s) - 1; i >= 0; i-- {
    if s[i] != ' ' && cnt[s[i]] == 1 { return s[i] }
  }
  return 0
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import java.util.*;
class Solution {
  public Character lastNonRepeatingChar(String s) {
    Map<Character, Integer> cnt = new HashMap<>();
    for (char c : s.toCharArray()) if (c != ' ') cnt.put(c, cnt.getOrDefault(c, 0) + 1);
    for (int i = s.length() - 1; i >= 0; i--) {
      if (s.charAt(i) != ' ' && cnt.get(s.charAt(i)) == 1) return s.charAt(i);
    }
    return null;
  }
}
1
2
3
4
5
6
7
8

class Solution:
  def last_non_repeating_char(self, s: str) -> str | None:
    from collections import Counter
    cnt = Counter(c for c in s if c != ' ')
    for i in range(len(s) - 1, -1, -1):
      if s[i] != ' ' and cnt[s[i]] == 1:
        return s[i]
    return None

Complexity

  • ⏰ Time complexity: O(n), since we scan the string twice.
  • 🧺 Space complexity: O(1) (if alphabet is fixed), otherwise O(n) for the hash map.