fork download 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 		new Ideone().run();
  13. 	}
  14.  
  15. 	String str1 = "spqrstrupvqw";
  16. 	String str2 = "sprt";
  17. 	String str3 = "q";
  18. 	char[] arr = str1.toCharArray();
  19. 	HashSet<Character> take = new HashSet<Character>();
  20. 	HashSet<Character> notTake = new HashSet<Character>();
  21. 	HashMap<Character, Integer> map = new HashMap<Character, Integer>();
  22.  
  23. 	void run()throws java.lang.Exception{
  24. 		System.out.println(str1 + " " + str2 + " " + str3);
  25.  
  26. 		//Add chars of str2 to a set to check if a char has to be taken in O(1)time.
  27. 		for(int i=0; i<str2.length(); i++){
  28. 			take.add(str2.charAt(i));
  29. 		}
  30.  
  31. 		//Add chars of str3 to a set to check if a char shouldn't be taken in O(1) time.
  32. 		for(int i=0; i<str3.length(); i++){
  33. 			notTake.add(str3.charAt(i));
  34. 		}
  35.  
  36. 		int last = -1;
  37. 		int bestStart = -1;
  38. 		int bestLength = arr.length+1;
  39.  
  40. 		// The window will be from [last....next]
  41.  
  42. 		for(int next=last+1; next<arr.length; next++){
  43. 			if(notTake.contains(arr[next])){ 
  44. 				last = initLast(next+1); //reinitialize the window's start. 
  45. 				next = last;
  46. 			}else if(take.contains(arr[next])){
  47. 				// take this character in the window and update count in map.
  48. 				if(last == -1){
  49. 					last = next;
  50. 					map.put(arr[last], 1);
  51. 				}else{
  52. 					if(!map.containsKey(arr[next])) map.put(arr[next], 1);
  53. 					else          map.put(arr[next], map.get(arr[next])+1);
  54. 				}
  55. 			}
  56.  
  57. 			if(last >= arr.length){ // If window is invalid
  58. 				break;
  59. 			}
  60.  
  61. 			if(last==-1){
  62. 				continue;
  63. 			}
  64.  
  65. 			//shorten window by removing chars from start that are already present.
  66. 			while(last <= next){
  67. 				char begin = arr[last];
  68.  
  69. 				// character is not needed in the window, ie not in set "take"
  70. 				if(!map.containsKey(begin)){
  71. 					last++;
  72. 					continue;
  73. 				}
  74.  
  75. 				// if this character already occurs in a later part of the window
  76. 				if(map.get(begin) > 1){
  77. 					last++;
  78. 					map.put(begin, map.get(begin)-1);
  79. 				}else{
  80. 					break;
  81. 				}
  82. 			}
  83.  
  84. 			// if all chars of str2 are in window and no char of str3 in window, 
  85.     // then update bestAnswer
  86. 			if(map.size() == str2.length()){
  87. 				int curLength = next - last + 1;
  88. 				if(curLength < bestLength){
  89. 					bestLength = curLength;
  90. 					bestStart  = last;
  91. 				}
  92. 			}
  93. 		}
  94.  
  95. 		if(bestStart==-1){
  96. 			System.out.println("there is no such window");
  97. 		}else{
  98. 			System.out.println("the window is from " + bestStart + " to " + (bestStart + bestLength-1));
  99. 			System.out.println("window " + str1.substring(bestStart, bestStart+bestLength));
  100. 		}
  101.  
  102. 	}
  103.  
  104. 	// Returns the first position in arr starting from index 'fromIndex'
  105. 	// such that the character at that position is in str2.
  106. 	int initLast(int fromIndex){
  107.  
  108. 		// clear previous mappings as we are starting a new window
  109. 		map.clear();
  110. 		for(int last=fromIndex; last<arr.length; last++){
  111. 			if(take.contains(arr[last])){
  112. 				map.put(arr[last], 1);
  113. 				return last;
  114. 			}
  115. 		}
  116. 		return arr.length;
  117. 	}
  118. }
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin 
Standard input is empty
stdout 
spqrstrupvqw sprt q
the window is from 4 to 8
window strup
https://ideone.com/gRchrJ
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!