Tag: leetcode

Given a string s, the task is to find the minimum characters to be added at the front to make the string palindrome.

Note: A palindrome string is a sequence of characters that reads the same forward and backward.

Examples:

Input: s = "abc"
Output: 2
Explanation: Add 'b' and 'c' at front of above string to make it palindrome : "cbabc"

Input: s = "aacecaaaa"
Output: 2
Explanation: Add 2 a's at front of above string to make it palindrome : "aaaacecaaaa"

Constraints:
1 <= s.size() <= 10⁶

Solution:

To determine the minimum characters to be added at the front of a string to make it a palindrome, we can solve the problem efficiently using a technique involving the longest prefix of the string that is also a suffix (LPS). This can be computed using the KMP algorithm. Below is the explanation, followed by the implementation.

Key Observation:

To make the string a palindrome by adding only characters to the front:

• We need to find the longest suffix of the string (starting at the end) that is already a palindrome.
• Once this suffix is identified, the remaining prefix of the string (which isn’t part of that palindromic suffix) will need to be reversed and added to the front of the string. The count of these characters is the output.

This amounts to finding:

1. The longest prefix-suffix (LPS) of the string concatenated with its reverse (using a special separator character to avoid false matches).

Let’s break this into steps.

Steps to Find the Minimum Characters:

1. Concatenate the String and Its Reverse:
   • Create a new string: temp = s + "$" + reverse(s) (we use $ or any separator to distinguish the reversed part from the original string).
2. Compute Longest Prefix Suffix (LPS):
   • Use the KMP (Knuth-Morris-Pratt) algorithm on temp to compute the LPS array.
   • The LPS array gives us the length of the longest prefix of temp that is also a suffix. This indicates the maximum part of s (from the start) that matches the reverse part.
3. Calculate Minimum Characters to Add:
   • Subtract the longest prefix-suffix from the length of the original string:

Minimum characters to add = s.length() - LPS[length of temp - 1]

Implementation in C++:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// Function to compute the LPS array (used in KMP algorithm)
vector<int> computeLPS(const string& str) {
    int n = str.length();
    vector<int> lps(n, 0); // LPS array
    int len = 0;          // Length of previous longest prefix suffix
    int i = 1;

    // Compute LPS array
    while (i < n) {
        if (str[i] == str[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1]; // Backtrack
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

// Function to find minimum characters to add at front to make the string palindrome
int minCharsToMakePalindrome(const string& s) {
    string reversedStr = s;
    reverse(reversedStr.begin(), reversedStr.end());

    // Create the concatenated string
    string temp = s + "$" + reversedStr;

    // Compute LPS array for the concatenated string
    vector<int> lps = computeLPS(temp);

    // Length of the longest palindromic suffix
    int longestPalindromicPrefix = lps.back();

    // Minimum characters to add = length of s - longest palindromic prefix
    return s.length() - longestPalindromicPrefix;
}

int main() {
    string s;
    cout << "Enter string: ";
    cin >> s;

    int result = minCharsToMakePalindrome(s);

    cout << "Minimum characters to add: " << result << endl;

    return 0;
}

Explanation of Code:

1. Reverse the String:
   • Create a reversed copy of s (reversedStr).
2. Concatenate s, $, and reversedStr:
   • This ensures we identify the longest part of s that matches the reversed portion.
   Example:
   If s = “aacecaaa”, then temp = “aacecaaa$aaacecaa”.
3. Compute LPS Array:
   • Use the KMP algorithm to compute the longest prefix that is also a suffix for temp.
4. Find the Num of Characters to Add:
   • Subtract the length of the longest palindromic prefix from the total length of s.

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 

Key Observations:

1. A rotated sorted array is a sorted array that has been rotated at some pivot point. For example:
   • Original array: [1, 2, 3, 4, 5]
   • Rotated arrays: [4, 5, 1, 2, 3], [3, 4, 5, 1, 2]
2. Minimum Element:
   • The minimum element is the only element in the rotated array that is smaller than its predecessor.
   • Alternatively, in the case of no rotation (e.g., [1, 2, 3, 4, 5]), the first element is the smallest.
3. Binary Search Approach:
   • Since the array is sorted and rotated, we can use binary search to identify the minimum element in O(log n) time.

Steps to Solve:

1. Binary Search:
   • Set two pointers: low = 0 (start of array) and high = n-1 (end of array).
   • While low < high, compute the middle index: mid = low + (high - low) / 2.
   • Depending on the relationship between arr[mid] and arr[high]:
     • If arr[mid] > arr[high]: The minimum must lie in the right half of the array (set low = mid + 1).
     • Otherwise, the minimum must be in the left half or at mid (set high = mid).
   • When low == high, the minimum element is at index low.
2. Return the Result:
   • Output the element at arr[low].

Algorithm Complexity:

• Time Complexity:
  Binary search operates in O(log n) time due to halving the search space in every iteration.
• Space Complexity:
  The algorithm uses O(1) space as we only manipulate indices and access the array directly.

Implementation in C++:

Here is the efficient implementation:

#include <iostream>
#include <vector>
using namespace std;

int findMinimum(const vector<int>& arr) {
    int low = 0, high = arr.size() - 1;

    // Binary search to find the minimum element
    while (low < high) {
        int mid = low + (high - low) / 2;

        // If middle element is greater than the last element,
        // the minimum must be in the right half
        if (arr[mid] > arr[high]) {
            low = mid + 1;
        } 
        // Otherwise, the minimum is in the left half (or could be at mid)
        else {
            high = mid;
        }
    }

    // At this point, low == high and points to the minimum element
    return arr[low];
}

int main() {
    vector<int> arr = {4, 5, 6, 7, 0, 1, 2}; // Example rotated array
    cout << "The minimum element is: " << findMinimum(arr) << endl;

    return 0;
}

Difficulty: Easy
Accuracy: 40.43%
Submissions: 262K+Points: 2

Given a string s consisting of lowercase Latin Letters. Return the first non-repeating character in s. If there is no non-repeating character, return ‘$’.
Note: When you return ‘$’ driver code will output -1.

Examples:

Input: s = "geeksforgeeks"
Output: 'f'
Explanation: In the given string, 'f' is the first character in the string which does not repeat.

Input: s = "racecar"
Output: 'e'
Explanation: In the given string, 'e' is the only character in the string which does not repeat.

Input: s = "aabbccc"
Output: -1
Explanation: All the characters in the given string are repeating.

Constraints:
1 <= s.size() <= 10⁵

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

char firstNonRepeatingChar(const string& s) {
    // Step 1: Count frequencies of each character
    unordered_map<char, int> charCount;
    for (char c : s) {
        charCount[c]++;
    }

    // Step 2: Find the first non-repeating character
    for (char c : s) {
        if (charCount[c] == 1) {
            return c; // First non-repeating character found
        }
    }

    // Step 3: No non-repeating character
    return '$';
}

int main() {
    string s = "geeksforgeeks";
    char result = firstNonRepeatingChar(s);

    if (result == '$') {
        cout << -1 << endl; // Follow the note: '$' indicates no non-repeating character
    } else {
        cout << result << endl;
    }

    return 0;
}

To solve the problem of finding the first non-repeating character in a string, we can use an efficient approach by incorporating a hashmap (or an equivalent data structure) to count the frequency of characters in the string. Here’s the step-by-step solution:

Steps to Solve:

1. Count Character Frequencies:
   • Traverse the string and count the occurrences of each character.
   • Store the counts in a dictionary (or a hashmap).
2. Find the First Non-Repeating Character:
   • Traverse the string again, and for each character, check its frequency in the hashmap.
   • The first character with a frequency of 1 is the first non-repeating character.
3. Return the Result:
   • If no character has a frequency of 1, return $.

Algorithm Complexity:

1. Time Complexity:
   • Counting frequencies: O(n) (single traversal for the frequency hashmap).
   • Traversing again to find the first non-repeating character: O(n).
   • Total: O(n).
2. Space Complexity:
   • Storing frequencies in a hashmap requires O(26) (in the worst case, since there are only 26 lowercase Latin letters). This is O(1) space.

Peak element

https://www.geeksforgeeks.org/problems/peak-element
https://leetcode.com/problems/find-peak-element
Difficulty: Basic
Accuracy: 38.86%
Submissions: 510K+Points: 1

Given an array arr[] where no two adjacent elements are same, find the index of a peak element. An element is considered to be a peak if it is greater than its adjacent elements (if they exist). If there are multiple peak elements, return index of any one of them. The output will be “true” if the index returned by your function is correct; otherwise, it will be “false”.

Note: Consider the element before the first element and the element after the last element to be negative infinity.

Examples :

Input: arr = [1, 2, 4, 5, 7, 8, 3]
Output: true
Explanation: arr[5] = 8 is a peak element because arr[4] < arr[5] > arr[6].

Input: arr = [10, 20, 15, 2, 23, 90, 80]
Output: true
Explanation: arr[1] = 20 and arr[5] = 90 are peak elements because arr[0] < arr[1] > arr[2] and arr[4] < arr[5] > arr[6]. 

Input: arr = [1, 2, 3]
Output: true
Explanation: arr[2] is a peak element because arr[1] < arr[2] and arr[2] is the last element, so it has negative infinity to its right.

Constraints:
1 ≤ arr.size() ≤ 10⁶
-2³¹ ≤ arr[i] ≤ 2³¹ – 1

Solution in C++

Algorithm: Uses a binary search approach to find a peak element in O(log n) time complexity.

//
// Created by robert on 12/15/24.
//
#include <iostream>
#include <vector>
using namespace std;

int findPeakElement(const vector<int>& arr) {
    int n = arr.size();
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        // Check if the mid element is a peak
        if ((mid == 0 || arr[mid] > arr[mid - 1]) &&
            (mid == n - 1 || arr[mid] > arr[mid + 1])) {
            return mid; // Peak found
        }

        // If the left neighbor is greater, search on the left side
        if (mid > 0 && arr[mid - 1] > arr[mid]) {
            high = mid - 1;
        }
        // Otherwise, search on the right side
        else {
            low = mid + 1;
        }
    }

    return -1; // This should never be reached
}

int main() {
    vector<int> arr = {1, 2, 4, 5, 7, 8, 3};
    int peakIndex = findPeakElement(arr);
    cout << "Peak element index: " << peakIndex << endl;
    return 0;
}