Cracking the Coding Interview | Problem #1.1 | By Awadh Kishor Singh

Is Unique: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

Approach 1 :

One common approach to solving this problem is to use additional data structures, such as a hash table or a set, to keep track of characters seen so far and to quickly check for duplicates. However, there's also a constraint sometimes added to the problem: you're not allowed to use any additional data structures.

Approach 2 :

In other words, the simplest approach involves a brute-force method where each character in the string is compared with every other character to check for duplicates. While this method is straightforward, it becomes increasingly inefficient as the length of the string grows. With a time complexity of O(N^2), where N is the length of the string, this approach becomes impractical for longer strings due to its quadratic time complexity. Therefore, it's not recommended for large inputs due to its inefficiency.

str = input()
for i in range(len(str)):
    flag = True
    for j in range(len(str)):
        if(i==j):
            continue
        else:
            if(str[i]==str[j]):
                print("NO, Not all Characters are unique.")
                flag = False
                break
    if(flag == False):
        break
if(flag==True):
    print("Yes, All the characters in stting are unique.")

Approach 3:

The approach behind this solution is relatively straightforward:

1. Sorting: The first step is to sort the array of integers. Sorting the array allows us to bring duplicate elements together, making it easier to identify them during the subsequent linear scan.

2. Linear Scan for Duplicates: After sorting, the algorithm iterates through the array once. During this iteration, it compares each element with its adjacent element. If any adjacent elements are found to be equal, it means that the array contains duplicates.

By sorting the array first, identical elements become adjacent to each other. This simplifies the process of identifying duplicates because duplicates will be consecutive after sorting. This approach leverages the fact that sorting algorithms typically have a time complexity of O(n log n), where n is the number of elements in the array. After sorting, the linear scan through the sorted array has a time complexity of O(n), resulting in an overall time complexity of O(n log n).

While this solution has a relatively efficient time complexity, it does modify the input array (by sorting it), which might not be desirable in all situations. However, if modifying the input array is acceptable, this approach provides a simple and effective way to determine if there are any duplicate elements in the array.

# include <bits/stdc++.h>
using namespace std;
int main()
{
    string str;
    cin>>str;
    sort(str.begin(),str.end());

    for (int i = 0; i < str.size() - 1; i++) 

   {

        if (str[i] == str[i + 1]) 
        {
            cout<<"NO , not unique"<<endl;
            return 0;  
        }

   }

    cout<<"Yes, It is unique"<<endl;
    return 0;  

}

Closing statements for a blog post about solving Problem 1.1 in "Cracking the Coding Interview" could summarize the key points discussed in the post and offer some final thoughts. Here's an example:

"In conclusion, Problem 1.1 from 'Cracking the Coding Interview' challenges us to determine if a string has all unique characters, without using additional data structures.

By understanding these concepts and practicing problem-solving techniques, you can become better prepared for technical interviews and real-world coding challenges. Remember to analyze the problem carefully, consider different approaches, and strive for efficiency in your solutions.

We hope this blog post has been informative and insightful. If you have any questions or would like to explore more coding interview problems, feel free to reach out or explore our other blog posts.

Twitter/X -- im_awadh_

LinkedIn -- imawadh

Instagram -- im_awadh_

Happy Coding!