🔸 Question
You receive a string. Confirm that each character occurs at most once. Then solve it again under a constraint: don’t allocate any additional data structures.
🔸 TL;DR
Scan the string with a simple double loop and compare each character with the ones after it. No sets, no tables—just O(n²) time and O(1) space, maximally readable ✅
🔸 One readable solution (Java, Unicode-safe)
if (s == null) return true;
for (int i = 0; i 〈 s.length(); ) {
int ci = s.codePointAt(i);
int nextI = i + Character.charCount(ci);
for (int j = nextI; j 〈 s.length(); ) {
int cj = s.codePointAt(j);
if (ci == cj) return false;
j += Character.charCount(cj);
}
i = nextI;
}
return true;
}
🔸 Why this is the best for readability (under the constraint)
▪️ Direct intent: “compare each character to those that follow; stop on a duplicate.”
▪️ No additional data structures—only a couple of loop indices.
▪️ Handles full Unicode via codePointAt (not just ASCII).
▪️ Easy to explain, easy to review, works everywhere.
🔸 Complexity
▪️ Time: O(n²) (worst/average)
▪️ Space: O(1)
🔸 Takeaways
▪️ When space is constrained, choose the clearest O(1)-space solution.
▪️ State assumptions (Unicode vs ASCII, case sensitivity) before coding.
▪️ Readability + correctness > premature cleverness. 🚀
#codinginterview #java #programming #algorithms #bigO #readablecode #interviewtips