Daily JavaScript Challenge #JS-185: Find First Repeated Character in a String
Welcome to Daily JavaScript Challenge #JS-185! Today, we’re diving into a common yet interesting string manipulation problem: finding the first repeated character in a string. This challenge will test your understanding of string traversal, character comparison, and potentially your knowledge of data structures like hash maps or sets for optimization. We’ll explore different approaches, analyze their time and space complexities, and provide a clear, well-documented JavaScript solution.
What We’ll Cover
- Understanding the Problem: Clearly defining the objective and edge cases.
- Naive Approach (Brute Force): A straightforward but potentially inefficient solution.
- Optimized Approach (Using Hash Map/Set): Leveraging data structures for better performance.
- JavaScript Code Implementation: Detailed, commented code examples.
- Time and Space Complexity Analysis: Understanding the performance implications.
- Test Cases: Thorough testing to ensure correctness.
- Alternative Solutions (if applicable): Exploring other approaches.
- Conclusion: Summarizing the key takeaways and encouraging further exploration.
1. Understanding the Problem
The problem is simple to state: Given a string, find the first character that appears more than once. If no character is repeated, return a specific value (e.g., null, -1, or an empty string) to indicate this.
Example:
- Input: “abcabcbb”
- Output: “a”
- Input: “abcdefg”
- Output: null (or -1, or “”)
Edge Cases to Consider:
- Empty string: Should return null (or -1, or “”).
- String with only one character: Should return null (or -1, or “”).
- String with all unique characters: Should return null (or -1, or “”).
- Case sensitivity: Decide whether to treat ‘a’ and ‘A’ as the same character. For this challenge, we’ll assume case sensitivity is required.
2. Naive Approach (Brute Force)
The brute-force approach involves iterating through the string and, for each character, checking if it appears again later in the string.
Algorithm:
- Iterate through the string using a nested loop.
- The outer loop iterates from the first character to the second-to-last character.
- The inner loop iterates from the character after the outer loop’s current character to the end of the string.
- If the characters at the outer and inner loop indices are the same, return the outer loop’s character.
- If the loops complete without finding a repeated character, return null (or -1, or “”).
JavaScript Code (Brute Force):
function findFirstRepeatedCharacterBruteForce(str) {
if (!str || str.length <= 1) {
return null;
}
for (let i = 0; i < str.length - 1; i++) {
for (let j = i + 1; j < str.length; j++) {
if (str[i] === str[j]) {
return str[i];
}
}
}
return null;
}
// Example usage:
console.log(findFirstRepeatedCharacterBruteForce("abcabcbb")); // Output: a
console.log(findFirstRepeatedCharacterBruteForce("abcdefg")); // Output: null
console.log(findFirstRepeatedCharacterBruteForce("")); // Output: null
console.log(findFirstRepeatedCharacterBruteForce("a")); // Output: null
Time Complexity (Brute Force): O(n^2), where n is the length of the string. This is because of the nested loops.
Space Complexity (Brute Force): O(1), as we're using only a constant amount of extra space.
3. Optimized Approach (Using Hash Map/Set)
The brute-force approach has a quadratic time complexity, which can be inefficient for longer strings. We can optimize this using a hash map (or a set in JavaScript) to keep track of the characters we've seen so far.
Algorithm:
- Create an empty set (or hash map).
- Iterate through the string character by character.
- For each character:
- Check if the character is already in the set.
- If it is, return the character.
- If it isn't, add the character to the set.
- If the loop completes without finding a repeated character, return null (or -1, or "").
Why use a Set or Hash Map? Sets and hash maps provide efficient lookups (typically O(1) on average), allowing us to quickly check if we've encountered a character before. This significantly reduces the time complexity compared to the brute-force approach.
JavaScript Code (Using Set):
function findFirstRepeatedCharacterOptimized(str) {
if (!str || str.length <= 1) {
return null;
}
const seenCharacters = new Set();
for (let i = 0; i < str.length; i++) {
const char = str[i];
if (seenCharacters.has(char)) {
return char;
}
seenCharacters.add(char);
}
return null;
}
// Example usage:
console.log(findFirstRepeatedCharacterOptimized("abcabcbb")); // Output: a
console.log(findFirstRepeatedCharacterOptimized("abcdefg")); // Output: null
console.log(findFirstRepeatedCharacterOptimized("")); // Output: null
console.log(findFirstRepeatedCharacterOptimized("a")); // Output: null
JavaScript Code (Using Hash Map - Object):
function findFirstRepeatedCharacterOptimizedMap(str) {
if (!str || str.length <= 1) {
return null;
}
const charMap = {}; // Using an object as a hash map
for (let i = 0; i < str.length; i++) {
const char = str[i];
if (charMap[char]) {
return char;
}
charMap[char] = true; // Mark the character as seen
}
return null;
}
// Example usage:
console.log(findFirstRepeatedCharacterOptimizedMap("abcabcbb")); // Output: a
console.log(findFirstRepeatedCharacterOptimizedMap("abcdefg")); // Output: null
console.log(findFirstRepeatedCharacterOptimizedMap("")); // Output: null
console.log(findFirstRepeatedCharacterOptimizedMap("a")); // Output: null
Time Complexity (Optimized): O(n), where n is the length of the string. We iterate through the string once.
Space Complexity (Optimized): O(n) in the worst case, where n is the length of the string. This is because, in the worst case, all characters in the string are unique, and the set (or hash map) will store all of them.
4. JavaScript Code Implementation
We've already provided the JavaScript code implementations for both the brute-force and optimized approaches. Let's reiterate with detailed comments:
Optimized Solution (Set):
/**
* Finds the first repeated character in a string using a Set.
*
* @param {string} str The input string.
* @returns {string | null} The first repeated character, or null if no character is repeated.
*/
function findFirstRepeatedCharacterOptimized(str) {
// Handle edge cases: empty string or string with only one character
if (!str || str.length <= 1) {
return null;
}
// Create a Set to store the characters we've seen. Sets provide O(1) average lookup time.
const seenCharacters = new Set();
// Iterate through the string character by character
for (let i = 0; i < str.length; i++) {
const char = str[i];
// Check if the character is already in the Set
if (seenCharacters.has(char)) {
// If it is, we've found the first repeated character, so return it
return char;
}
// If the character is not in the Set, add it to the Set
seenCharacters.add(char);
}
// If we reach the end of the string without finding a repeated character, return null
return null;
}
// Example usage:
console.log(findFirstRepeatedCharacterOptimized("abcabcbb")); // Output: a
console.log(findFirstRepeatedCharacterOptimized("abcdefg")); // Output: null
console.log(findFirstRepeatedCharacterOptimized("")); // Output: null
console.log(findFirstRepeatedCharacterOptimized("a")); // Output: null
Optimized Solution (Hash Map - Object):
/**
* Finds the first repeated character in a string using a hash map (object).
*
* @param {string} str The input string.
* @returns {string | null} The first repeated character, or null if no character is repeated.
*/
function findFirstRepeatedCharacterOptimizedMap(str) {
// Handle edge cases: empty string or string with only one character
if (!str || str.length <= 1) {
return null;
}
// Create an object to act as a hash map. Object properties provide fast lookups.
const charMap = {};
// Iterate through the string character by character
for (let i = 0; i < str.length; i++) {
const char = str[i];
// Check if the character is already in the hash map
if (charMap[char]) {
// If it is, we've found the first repeated character, so return it
return char;
}
// If the character is not in the hash map, add it to the hash map and mark it as seen
charMap[char] = true; // We can store any value here; 'true' is a common convention
}
// If we reach the end of the string without finding a repeated character, return null
return null;
}
// Example usage:
console.log(findFirstRepeatedCharacterOptimizedMap("abcabcbb")); // Output: a
console.log(findFirstRepeatedCharacterOptimizedMap("abcdefg")); // Output: null
console.log(findFirstRepeatedCharacterOptimizedMap("")); // Output: null
console.log(findFirstRepeatedCharacterOptimizedMap("a")); // Output: null
5. Time and Space Complexity Analysis
Let's summarize the time and space complexities of the different approaches:
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force | O(n^2) | O(1) |
| Optimized (Set) | O(n) | O(n) |
| Optimized (Hash Map) | O(n) | O(n) |
Key Takeaways:
- The optimized approaches (using a Set or a Hash Map) significantly improve the time complexity from O(n^2) to O(n).
- The trade-off is an increase in space complexity from O(1) to O(n). This is because we need to store the characters we've seen in the Set or Hash Map.
6. Test Cases
Thorough testing is crucial to ensure the correctness of our solution. Here are some test cases to consider:
- Basic case with repeated character: "abcabcbb" (Expected: "a")
- No repeated character: "abcdefg" (Expected: null)
- Empty string: "" (Expected: null)
- String with one character: "a" (Expected: null)
- Repeated character at the beginning: "aabbcc" (Expected: "a")
- Repeated character at the end: "abcdd" (Expected: "d")
- String with only repeated characters: "aaaaaa" (Expected: "a")
- String with mixed case (if case-sensitive): "aAbBcC" (Expected: null, as 'a' and 'A' are different)
- String with special characters: "abc!@#abc" (Expected: "a")
- Long string with few repetitions: A long string like "abcdefghijklmnopqrstuvwxyzabcdefgh" (Expected: "a") - this tests performance.
Example Test Execution (Optimized - Set):
function testFindFirstRepeatedCharacter(func) {
const testCases = [
{ input: "abcabcbb", expected: "a" },
{ input: "abcdefg", expected: null },
{ input: "", expected: null },
{ input: "a", expected: null },
{ input: "aabbcc", expected: "a" },
{ input: "abcdd", expected: "d" },
{ input: "aaaaaa", expected: "a" },
{ input: "aAbBcC", expected: null },
{ input: "abc!@#abc", expected: "a" },
{ input: "abcdefghijklmnopqrstuvwxyzabcdefgh", expected: "a" },
];
for (let i = 0; i < testCases.length; i++) {
const testCase = testCases[i];
const actual = func(testCase.input);
if (actual === testCase.expected) {
console.log(`Test Case ${i + 1}: Passed`);
} else {
console.error(`Test Case ${i + 1}: Failed. Expected: ${testCase.expected}, Actual: ${actual}`);
}
}
}
// Run the tests with the optimized Set solution
testFindFirstRepeatedCharacter(findFirstRepeatedCharacterOptimized);
// Run the tests with the optimized Map solution
testFindFirstRepeatedCharacter(findFirstRepeatedCharacterOptimizedMap);
7. Alternative Solutions (if applicable)
While the Set and Hash Map approaches are generally the most efficient, there might be slightly different variations. For example:
- Using `indexOf` in a loop (less efficient but potentially readable): You could iterate through the string and, for each character, use `str.indexOf(char, i + 1)` to check if the character appears again later in the string. This would still have a time complexity close to O(n^2) in the worst case, but it might be easier to understand for some. This is essentially a more readable version of the brute force approach.
Example (indexOf):
function findFirstRepeatedCharacterIndexOf(str) {
if (!str || str.length <= 1) {
return null;
}
for (let i = 0; i < str.length; i++) {
const char = str[i];
if (str.indexOf(char, i + 1) !== -1) {
return char;
}
}
return null;
}
console.log(findFirstRepeatedCharacterIndexOf("abcabcbb"));
console.log(findFirstRepeatedCharacterIndexOf("abcdefg"));
Important Note: This `indexOf` approach is generally less performant than the Set or Hash Map solutions and is included primarily for demonstration purposes.
8. Conclusion
In this Daily JavaScript Challenge #JS-185, we explored the problem of finding the first repeated character in a string. We discussed:
- A brute-force approach with O(n^2) time complexity and O(1) space complexity.
- An optimized approach using a Set or Hash Map with O(n) time complexity and O(n) space complexity.
- Detailed JavaScript code implementations with comments.
- Thorough testing with various test cases.
- A less efficient alternative solution using `indexOf`.
The key takeaway is that using appropriate data structures (like Sets or Hash Maps) can significantly improve the performance of your code, especially when dealing with string manipulation problems. Understanding the trade-offs between time and space complexity is crucial for writing efficient and scalable algorithms.
Keep practicing and exploring different JavaScript challenges! Happy coding!
Further Exploration
- Try implementing the solution using different programming languages.
- Explore variations of the problem, such as finding the *k*-th repeated character.
- Consider how you might adapt the solution to handle Unicode characters correctly.
```
