Repeated Character Whose First Appearance is Leftmost


Given a string, find the repeated character present first in the string.


Examples:


Input  : geeksforgeeks
Output : g
(mind that it will be g, not e.)

Input  : abcdabcd
Output : a

Input  : abcd
Output : -1
No character repeats

Asked in: Goldman Sachs internship

We have discussed different approaches in Find repeated character present first in a string.

How to solve this problem using one traversal of input string?


Method 1 (Traversing from Left to Right)
We traverse the string from left to right. We keep track of the leftmost index of every character. If a character repeats, we compare its leftmsot index with current result and update the result if result is greater

#include <bits/stdc++.h>

using namespace std;

#define NO_OF_CHARS 256

  

int firstRepeating(string& str)

{

    

    

    int firstIndex[NO_OF_CHARS];

    for (int i = 0; i < NO_OF_CHARS; i++)

        firstIndex[i] = -1;

  

    

    

    

    

    int res = INT_MAX;

    for (int i = 0; i < str.length(); i++) {

        if (firstIndex[str[i]] == -1)

           firstIndex[str[i]] = i;

        else

           res = min(res, firstIndex[str[i]]);

    }

  

    return (res == INT_MAX) ? -1 : res;

}

  

int main()

{

    string str = "geeksforgeeks";

    int index = firstRepeating(str);

    if (index == -1)

        printf("Either all characters are "

               "distinct or string is empty");

    else

        printf("First Repeating character"

               " is %c",

               str[index]);

    return 0;

}

Output:


First Repeating character is g

Time Complexity : O(n). It does only one traversal of input string.
Auxiliary Space : O(1)


Method 2 (Traversing Right to Left)
We traverse the string from right to left. We keep track of the visited characters. If a character repeats, we update the result.

#include <bits/stdc++.h>

using namespace std;

#define NO_OF_CHARS 256

  

int firstRepeating(string& str)

{

    

    bool visited[NO_OF_CHARS];

    for (int i = 0; i < NO_OF_CHARS; i++)

        visited[i] = false;

  

    

    

    int res = -1;

    for (int i = str.length() - 1; i >= 0; i--) {

        if (visited[str[i]] == false)

            visited[str[i]] = true;

        else

            res = i;

    }

  

    return res;

}

  

int main()

{

    string str = "geeksforgeeks";

    int index = firstRepeating(str);

    if (index == -1)

        printf("Either all characters are "

               "distinct or string is empty");

    else

        printf("First Repeating character"

               " is %c",

               str[index]);

    return 0;

}

Output:


First Repeating character is g

Time Complexity : O(n). It does only one traversal of input string.
Auxiliary Space : O(1)

The method 2 is better than method 1 as it does fewer comparisons.




If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please Improve this article if you find anything incorrect by clicking on the “Improve Article” button below.

Article Tags :



1

Please write to us at contribute@geeksforgeeks.org to report any issue with the above content.








Source link

Python | Bigram formation from given list


When we are dealing with text classification, sometimes we need to do certain kind of natural language processing and hence sometimes require to form bigrams of words for processing. In case of absence of appropriate library, its difficult and having to do the same is always quite useful. Let’s discuss certain ways in which this can be achieved.

Method #1 : Using list comprehension + enumerate() + split()
The combination of above three functions can be used to achieve this particular task. The enumerate function performs the possible iteration, split function is used to make pairs and list comprehension is used to combine the logic.

   

test_list = ['geeksforgeeks is best', 'I love it']

  

print ("The original list is : " + str(test_list))

  

res = [(x, i.split()[j + 1]) for i in test_list 

       for j, x in enumerate(i.split()) if j < len(i.split()) - 1]

  

print ("The formed bigrams are : " + str(res))

Output :

The original list is : [‘geeksforgeeks is best’, ‘I love it’]
The formed bigrams are : [(‘geeksforgeeks’, ‘is’), (‘is’, ‘best’), (‘I’, ‘love’), (‘love’, ‘it’)]

 
Method #2 : Using zip() + split() + list comprehension
The task that enumerate performed in the above method can also be performed by the zip function by using the iterator and hence in a faster way. Let’s discuss certain ways in which this can be done.

   

test_list = ['geeksforgeeks is best', 'I love it']

  

print ("The original list is : " + str(test_list))

  

res = [i for j in test_list 

       for i in zip(j.split(" ")[:-1], j.split(" ")[1:])]

  

print ("The formed bigrams are : " + str(res))

Output :

The original list is : [‘geeksforgeeks is best’, ‘I love it’]
The formed bigrams are : [(‘geeksforgeeks’, ‘is’), (‘is’, ‘best’), (‘I’, ‘love’), (‘love’, ‘it’)]




If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please Improve this article if you find anything incorrect by clicking on the “Improve Article” button below.

Article Tags :



Be the First to upvote.

Please write to us at contribute@geeksforgeeks.org to report any issue with the above content.








Source link

Python | Convert case of elements in a list of strings


Given a list of strings, write a Python program to convert all string from lowercase/uppercase to uppercase/lowercase.

Input : ['GeEk', 'FOR', 'gEEKS']
Output: ['geeks', 'for', 'geeks']

Input : ['fun', 'Foo', 'BaR']
Output: ['FUN', 'FOO', 'BAR']

 
Method #1 : Convert Uppercase to Lowercase using map function

  

out = map(lambda x:x.lower(), ['GeEk', 'FOR', 'gEEKS'])

  

output = list(out)

  

print(output)

Output:


['geek', 'for', 'geeks']

 
Method #2: Convert Lowercase to Uppercase using List comprehension

  

input = ['fun', 'Foo', 'BaR']

  

lst = [x.upper() for x in input]

  

print(lst)

Output:


['FUN', 'FOO', 'BAR']




If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please Improve this article if you find anything incorrect by clicking on the “Improve Article” button below.

Article Tags :



Be the First to upvote.

Please write to us at contribute@geeksforgeeks.org to report any issue with the above content.











Source link