Check if a character is only occurring as one single contiguous substring or not
Given string str of length N. The task is to determine whether a character is only occurring as a single contiguous substring or not i.e., there should not exist any other alphabet characters in between two same alphabets in the string.
Examples:
Input: “aAa”
Output: False
Explanation: There exists ‘A’ in between ‘a’ and ‘a’. Hence “aa” becomes discontinuous.Input: “aaAAbbBB”
Output: True
Explanation: Different segments formed from the given input are “aa”, “AA”, “bb” and “BB” are all continuous and have no hurdles in between.
Approach: To solve the given problem use the following idea:
Store the last occurrence of each character in Hash-Map so that it can be compared with its previous occurrence and find the distance between them. If this distance comes to be more than 1 then it is discontinuous else continuous.
Follow the given steps to solve the given problem:
- Traverse string str (say i).
- If str[i] is present in the map
- If the difference between the last occurrence and (i + 1) is equal to 1 then update the last occurrence of the i-th character.
- Else return false.
- Else update the last occurrence of i-th character in the Hash map as (i + 1).
- Return True after the loop is over.
Below is the implementation for the above approach:
C++14
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; bool isContinuous(string& temp) { // Creating Hashmap to store the // last position of a character unordered_map< char , int > last_Pos; for ( int i = 0; i < temp.length(); i++) { // if character is already // present in Hashmap if (last_Pos[temp[i]]) { // if the last position of the // character is previous index // update last position if (i - last_Pos[temp[i]] + 1 <= 1) { last_Pos[temp[i]] = i + 1; } else { return 0; } } else { last_Pos[temp[i]] = i + 1; } } return 1; } // Driver code int main() { string str = "aaAAbbBB" ; if (isContinuous(str)) { cout << "True" ; } else { cout << "False" ; } return 0; } // this code is contributed by prophet1999 |
Java
// Java code for the above approach import java.io.*; import java.util.*; class GFG { static boolean isContinuous(String temp) { // Creating Hashmap to store the last position of a // character HashMap<Character, Integer> last_Pos = new HashMap<Character, Integer>(); for ( int i = 0 ; i < temp.length(); i++) { // if character is already present in Hashmap if (last_Pos.containsKey(temp.charAt(i))) { // if the last position of the character is // previous index update last position if (i - last_Pos.get(temp.charAt(i)) + 1 <= 1 ) { last_Pos.put(temp.charAt(i), i + 1 ); } else { return false ; } } else { last_Pos.put(temp.charAt(i), i + 1 ); } } return true ; } public static void main(String[] args) { String str = "aaAAbbBB" ; if (isContinuous(str)) { System.out.print( "True" ); } else { System.out.print( "False" ); } } } // This code is contributed by lokeshmvs21. |
Python3
# Python3 code for the above approach def isContinuous(temp) : # Creating Hashmap to store the # last position of a character last_Pos = dict .fromkeys(temp, 0 ); for i in range ( len (temp)) : # if character is already # present in Hashmap if (last_Pos[temp[i]]) : # if the last position of the # character is previous index # update last position if (i - last_Pos[temp[i]] + 1 < = 1 ) : last_Pos[temp[i]] = i + 1 ; else : return 0 ; else : last_Pos[temp[i]] = i + 1 ; return 1 ; # Driver code if __name__ = = "__main__" : string = "aaAAbbBB" ; if (isContinuous(string)) : print ( "True" ); else : print ( "False" ); # This code is contributed by AnkThon |
C#
// Include namespace system using System; using System.Collections.Generic; using System.Collections; public class GFG { public static bool isContinuous(String temp) { // Creating Hashmap to store the last position of a // character var last_Pos = new Dictionary< char , int >(); for ( int i = 0; i < temp.Length; i++) { // if character is already present in Hashmap if (last_Pos.ContainsKey(temp[i])) { // if the last position of the character is // previous index update last position if (i - last_Pos[temp[i]] + 1 <= 1) { last_Pos[temp[i]] = i + 1; } else { return false ; } } else { last_Pos[temp[i]] = i + 1; } } return true ; } public static void Main(String[] args) { var str = "aaAAbbBB" ; if (GFG.isContinuous(str)) { Console.Write( "True" ); } else { Console.Write( "False" ); } } } // This code is contributed by adityapburujwale |
Javascript
<script> // Javascript code for the above approach function isContinuous(temp) { // Creating Hashmap to store the // last position of a character let last_Pos = new Map(); for (let i = 0; i < temp.length; i++) { // if character is already // present in Hashmap if (last_Pos.get(temp[i])) { // if the last position of the // character is previous index // update last position if (i - last_Pos.get(temp[i]) + 1 <= 1) { last_Pos.set(temp[i], i + 1); } else { return 0; } } else { last_Pos.set(temp[i], i + 1); } } return 1; } // Driver code let str = "aaAAbbBB" ; if (isContinuous(str)) { document.write( "True" ); } else { document.write( "False" ); } // this code is contributed by Saurabh Jaiswal </script> |
True
Time Complexity: O(N)
Auxiliary Space: O(N)