Akuna Capital·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Akuna Capital coding round, one problem the whole session. Algorithmic but not purely mechanical, they wanted the full explanation plus proof of correctness which I was not expecting.

Questions Asked (1)

You're given a palindromic string of lowercase letters. Change exactly one character so the result is not a palindrome and is lexicographically smallest among all valid options. Return an empty string if it's impossible. Walk through your algorithm, prove it's correct, and give time and space complexity. Code it up too.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The base problem clicked pretty fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem constraints and edge cases (e.g., single-character string, all same characters). Then, design a greedy algorithm that scans from left to right, replacing the first non-'a' character with 'a' if it's not the middle character in an odd-length palindrome; if all characters are 'a', change the last character to 'b'. Finally, prove correctness by showing the greedy choice yields the lexicographically smallest non-palindrome, and analyze time and space complexity.

Pro tip: Explicitly handle the edge case where the string consists entirely of 'a's (e.g., 'aaa') by changing the last character to 'b', and mention that for odd-length palindromes, changing the middle character keeps it a palindrome, so it must be avoided.

1. Clarify constraints and edge cases

Ask about input size, character set, and whether the string is guaranteed to be a palindrome. Identify edge cases: length 1, all characters identical, and odd-length with middle character.

2. Design greedy algorithm

Scan from left to right. For each index i, if s[i] != 'a' and (n is even or i != n//2), change s[i] to 'a' and return. If no such index, change the last character to 'b' (if n>1) or return empty string (if n=1).

3. Prove correctness

Argue that changing the earliest possible non-'a' to 'a' yields the lexicographically smallest string because 'a' is the smallest letter. Ensure the change does not produce a palindrome by avoiding the middle character in odd-length strings.

4. Analyze complexity

Time complexity is O(n) for a single scan, and space complexity is O(n) if creating a new string, or O(1) if modifying in place (with mutable input).

5. Implement and test

Write clean code with comments, and test with cases: 'abba' -> 'aaba', 'aaaa' -> 'aaab', 'a' -> '', 'aba' -> 'aaa'? Wait, 'aba' -> change middle? No, middle change keeps palindrome, so change first 'a'? Actually 'aba': indices 0 and 2 are 'a', index 1 is 'b' but middle, so cannot change. All non-middle are 'a', so change last to 'b' -> 'abb'? But 'abb' is not palindrome and lexicographically smallest? Compare with changing first to 'b' -> 'bba' which is larger. So 'abb' is correct. Test thoroughly.

Key Points to Mention

Greedy strategy: replace the first non-'a' character with 'a' to minimize lexicographic order.
Avoid changing the middle character in odd-length palindromes to prevent remaining a palindrome.
Edge case: all characters are 'a' (e.g., 'aaaa'), change the last character to 'b'.
Edge case: single-character string, return empty string.
Time complexity O(n) and space complexity O(n) or O(1) depending on implementation.
Proof of correctness: the first change that makes the string non-palindromic and uses the smallest possible character yields the lexicographically smallest result.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.